Page 1 of 7
10004,please tell me where is my fault!
Posted: Mon Jul 29, 2002 7:46 pm
by zyzyis
[cpp]
#include <iostream.h>
int graph[200][200];
int color[200];
int re[200];
int key;
void Init();
int Check(int,int,int);
void Backtrance(int,int);
void main()
{
int nodenum=0;
cin>>nodenum;
int num=0;
while(nodenum!=0)
{
int line=0;
int x=0;
int y=0;
Init();
cin>>line;
for (int i=0; i<line; i++)
{
cin>>x>>y;
graph[x][y]=1;
graph[y][x]=1;
}
Backtrance(nodenum,0);
if (key)
{
re[num]=1;
}
cin>>nodenum;
key=0;
num++;
}
for (int i=0; i<num; i++)
{
if (!re
)
cout<<"NOT BICOLORABLE.";
else
cout<<"BICOLORABLE.";
cout<<endl;
}
}
void Init()
{
for (int i=0; i<200; i++)
{
color=-1;
re=0;
for (int j=0; j<200; j++)
{
graph[j]=0;
}
}
}
void Backtrance(int nodenum,int n)
{
if (n==nodenum)
{
key=1;
return;
}
for (int i=0; i<=1; i++)
{
if (Check(n,i,nodenum))
{
color[n]=i;
Backtrance(nodenum,n+1);
if (key)
return;
}
}
}
int Check(int beg,int c,int nodenum)
{
for (int i=0; i<nodenum; i++)
{
if (beg==i)
continue;
if ((graph[beg])&&(color==c))
return 0;
}
return 1;
}
[/cpp]
///thank u very much!!! 
[/cpp]
Posted: Fri Sep 20, 2002 2:33 pm
by henar2
I don't know where is your fault.
I just want to ask what is the algorithm used to solve this problem.
Could somebody explain to me?
Thanks.
Posted: Fri Sep 20, 2002 6:35 pm
by Picard
zyzyis: it's probably too late, but you clear re[] array with Init() at every test case. btw why are you saving the result in re[]? why not print it right away?
henar2: you can fill the graph (starting from any node, coloring to color1), fill all neighbours to the other color (recursivly). during filling when a node was assigned earlier a different color -> not bicolorable. otherwise if all node are filled -> bicolorable.
Posted: Fri Sep 20, 2002 8:32 pm
by arnsfelt
Also, the graph need not to be connected. So one may need to start the recursion several times.
Posted: Fri Sep 20, 2002 9:05 pm
by Picard
from the problem desc:
"the graph will be strongly connected. That is, there will be at least one path from any node to any other node."
Posted: Fri Sep 20, 2002 10:19 pm
by arnsfelt
oops, should have read the description again. Just relied on my vague memory ...
10004(Bicoloring)
Posted: Sun Nov 03, 2002 7:18 am
by lowai
A easy problem, i think. but I got WA. Is there any trick?
[pascal]
var
g : array[0..200, 0..200]of boolean;
color : array[0..200]of byte;
n : byte;
quit : boolean;
procedure init;
var i, e, j, k : integer;
begin
readln(n);
readln(e);
if n = 0 then halt;
fillchar(g, sizeof(g), false);
for i := 1 to e do
begin
readln(j, k);
g[j, k] := true;
g[k, j] := true;
end;
end;
procedure coloring(l, c : byte);
var i : byte;
begin
if quit then exit;
color[l] := c;
for i := 0 to n do
if not quit then
if g[l, i] then
if color = 0 then
coloring(i, 3 - c)
else
if color <> 3 - c then
begin quit := true; exit; end;
end;
begin
while true do
begin
init;
fillchar(color, sizeof(color), 0);
quit := false;
coloring(0, 1);
if not quit then
writeln('BICOLORABLE.')
else
writeln('NOT BICOLORABLE.');
end;
end.
[/pascal]
Posted: Sun Nov 03, 2002 3:53 pm
by jpfarias
Hi!
The general solution for this problem looks like this:
Code: Select all
1. Start at any point and colour it with color 1;
2. Colour all it's neighbour with color 2;
3. For each uncolored point:
4. Colour it with color 1;
5. If any of it's neighbour is colored with color 1 then
6. Colour it with colour 2
7. If any of it's neighbour is colored with color 2 then
8. It's not bocolorable
9. End
10. Colour all it's neighbour with color 1
11. Colour all it's neighbour with color 2
12. Return to 3 until all point's are colored
13. It's bicolorable
I used dfs to solve this problem, here is my function:
[cpp]
int dfs(int v, int colorAt=1)
{
pass[v]=colorAt;
int lcolor=colorAt;
colorAt=(colorAt==1?2:1);
int r=1;
for(int i=0;i<n;i++)
{
if (matrix[v]
)
{
if (!pass)
r=dfs(i,colorAt);
else if (pass==lcolor)
return 0;
}
}
return r;
}
[/cpp]
Hope I've helped!
Jo
Posted: Mon Nov 04, 2002 2:07 am
by lowai
I did it in the same way.
Posted: Mon Dec 02, 2002 11:02 am
by Astrakan
lowai: When I compile with gpc and run your program on a Linux machine, I get the following error message at the end of the output:
Code: Select all
./10004: attempt to read past end of Input (error #454 at 8049c1c)
The error is in procedure init, because you try to read in a value to e even if n is zero (end of input). Try swapping the two lines like this:
Code: Select all
procedure init;
var i, e, j, k : integer;
begin
readln(n);
if n = 0 then halt; {this line has been placed before...}
readln(e); {...this line}
fillchar(g, sizeof(g), false);
...
10004
Posted: Mon Mar 31, 2003 9:16 pm
by Hisoka
I always got WA for this problem, can you give me more test case?
Thanks.....
Posted: Tue Apr 01, 2003 4:00 am
by Hisoka
I debug my program again, and finaly I know where my mistake. Now I got AC
-Sorry-
10004
Posted: Sat Aug 23, 2003 2:59 am
by passwd
hi,
I
try this test case
Posted: Sat Aug 23, 2003 10:20 am
by Nick
4
4
0 1
1 2
2 3
3 0
5
5
0 1
1 2
2 3
3 4
4 0
3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0
output :
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
[/quote]
Posted: Fri Aug 29, 2003 3:23 am
by passwd
my program is working OK for this input ...
Can someone give-me some inputs that my program doesn