10004 - Bicoloring

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
zyzyis
New poster
Posts: 1
Joined: Mon Jul 29, 2002 7:37 pm
Contact:

10004,please tell me where is my fault!

Post by zyzyis » Mon Jul 29, 2002 7:46 pm

[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
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

Post by henar2 » Fri Sep 20, 2002 2:33 pm

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
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by Picard » Fri Sep 20, 2002 6:35 pm

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
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Post by arnsfelt » Fri Sep 20, 2002 8:32 pm

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

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by Picard » Fri Sep 20, 2002 9:05 pm

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
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Post by arnsfelt » Fri Sep 20, 2002 10:19 pm

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

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

10004(Bicoloring)

Post by lowai » Sun Nov 03, 2002 7:18 am

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
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Sun Nov 03, 2002 3:53 pm

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
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

Post by lowai » Mon Nov 04, 2002 2:07 am

I did it in the same way.

Astrakan
New poster
Posts: 24
Joined: Sun Nov 03, 2002 12:18 pm
Location: Sweden

Post by Astrakan » Mon Dec 02, 2002 11:02 am

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
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

10004

Post by Hisoka » Mon Mar 31, 2003 9:16 pm

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

Thanks..... :cry:

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Tue Apr 01, 2003 4:00 am

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

-Sorry-

passwd
New poster
Posts: 14
Joined: Thu Dec 05, 2002 11:20 pm

10004

Post by passwd » Sat Aug 23, 2003 2:59 am

hi,

I

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

try this test case

Post by Nick » Sat Aug 23, 2003 10:20 am

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
New poster
Posts: 14
Joined: Thu Dec 05, 2002 11:20 pm

Post by passwd » Fri Aug 29, 2003 3:23 am

my program is working OK for this input ...

Can someone give-me some inputs that my program doesn

Post Reply

Return to “Volume 100 (10000-10099)”