10004 - Bicoloring

[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]

[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.

[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.

[arnsfelt]

Also, the graph need not to be connected. So one may need to start the recursion several times.

[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."

[arnsfelt]

oops, should have read the description again. Just relied on my vague memory ...

[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]

[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

[lowai]

I did it in the same way.

[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);
...

[Hisoka]

I always got WA for this problem, can you give me more test case?

Thanks.....

[Hisoka]

I debug my program again, and finaly I know where my mistake. Now I got AC

-Sorry-

[passwd]

hi,

I

[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]

[passwd]

my program is working OK for this input ...

Can someone give-me some inputs that my program doesn