## 10004 - Bicoloring

Moderator: Board moderators

Picard, I have done as same as you have described But I got WA too many times and for many days.. i cant understand why.. and Im really confused with this problem.
Sajid Online: www.sajidonline.com
Sajid
Learning poster

Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.

### 10004 Bicoloring

Okay, I have ran every single possible graph I can concieve of and have produced the correct solution for that graph, which i painly checked each one on paper.

My current algorithem is just color the first graph node place him on a stack and pop him get the oppisite of his color and color the connected nodes and all newly colored nodes go on the stack, if by chance the cell is already colored I check to make sure that its the same color as what I am trying to color it with, if not print NOT BICOLORABLE., and if the stack emptys I succeeded and I print BICOLORABLE.

So, if anyone has a clue as to what I am doing wrong or a graph that might break my program, or some examples of you produced output I would appreciate it very much.

Thank You.
Doom_Gaze
New poster

Posts: 1
Joined: Thu Nov 20, 2003 7:52 pm

Isn't the algm. just to check if the graph is a bipartite graph or not ... i.e if there are no odd cycles ????
Putting n programmers on a problem will not result in the time of solving the problem to reduce by n.
murtaza
New poster

Posts: 7
Joined: Tue Jul 20, 2004 7:42 pm
Location: India

### 10004, Bicoloring - testcases or algorithm-review?!

Salut!

Today doesn't seem to be one of my best days - after having turned away from "Tug of War" (see other posting), I just thought I try to solve "Bicoloring" (10004)...

I'm trying to solve it with a quite simple algortihm:

I read in the nodes and their connections (parent - child) and afterwards color the graph, starting with the parent with the lowest number, coloring all of it's childs in the other color. Afterwards I take the next parent, again coloring all of each childs (if they are uncolored by this moment - if they have already been colored, I don't do anything to them).
After having colored the whole graph this way,
I scan over it and compare the parent - child pairs, searching, if there is one in that both have the same color.
If this happens, I break the procedure, give "NON BICOLORABLE" as output and get back to the beginning, waiting for further input.

Does anybody see a case in that this won't work - of can anybody give me just some more (possibly critical or tricky) testcases, please?!

I've added my code (in C) after this posting, perhaps does anybody see the reason for the WA...

Thanks again,

Tarek.

______________

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{

int numberOfNodes;
int numberOfEdges;
int i;
int j;
int color;
int parent;
int child;
int nodeInvolved[200];
int nodeConnections[200][200];
int nodeColor[200];

(void) scanf("%d", &numberOfNodes);

while (numberOfNodes) {

scanf("%d", &numberOfEdges);

for (i = 0; i < 200; i++) {
for (j = 0; j < 200; j++) {
nodeConnections[i][j] = 0;
}
}

for (i = 0; i < 200; i++) {
nodeColor[i] = 0;
nodeInvolved[i] = 0;
}

for (i = 0; i < numberOfEdges; i++) {
(void) scanf("%d", &parent);
(void) scanf("%d", &child);

nodeInvolved[parent] = 1;
nodeConnections[parent][child] = 1;
}

color = 1;

for (i = 0; i < 200; i++) {
if (nodeInvolved[i] == 1) {
for (j = 0; j < 200; j++) {
if (nodeConnections[i][j] == 1) {
if (nodeColor[j] == 0) {
nodeColor[j] = color;
}
}
}
if (color == 1) {
color = 2;
}
else if (color == 2) {
color = 1;
}
}
}

for (i = 0; i < 200; i++) {
if (nodeInvolved[i]) {
for (j = 0; j < 200; j++) {
if (nodeConnections[i][j]) {
if (nodeColor[i] == nodeColor[j]) {
printf("NOT BICOLORABLE.\n");
goto loop;
}
}
}
}
}

printf("BICOLORABLE.\n");

loop:
(void) scanf("%d", &numberOfNodes);
}

return 0;
}
One for all, and all for one!
jeu blanc
New poster

Posts: 2
Joined: Wed Mar 23, 2005 11:41 am
Location: Germany

Use the Search link above to check the pervious posts of the problem before posting..
if u can think of it .. u can do it in software.
Learning poster

Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

I use Floyd-Worshall to search if there is any circle (a path from a node to itself) with odd nodes. If there is, return no. And I get AC.

Yile
New poster

Posts: 17
Joined: Sun Feb 27, 2005 10:36 am
Location: China

### 10004

Can anyone give me a test this fails on?
It seems like an easy problem, but can't get A/C.

//Jared Johnson
//Bicoloring - 110901/10004

#include<iostream>
using namespace std;

//3 is not colored yet
bool graph[200][200];
int color[200];
int num_edges, num_vertices;

bool dfs(int v,int c) {
color[v]=c;
bool return_value=true;

for(int i=0; i<num_vertices; i++)
if(graph[v][i]) {
if(color[i]==3) {
if(!dfs(i, 1-c))
return false;
}
else if(color[i]==c) {
return false;
}
}

return return_value;
}

bool colorGraph() {
for(int i=0; i<num_vertices; i++)
color[i] = 3;
for(int i=0; i<num_vertices; i++)
if(color[i] == 3)
if(!dfs(i,0))
return false;
return true;
}

int main(int argc, char* argv[])
{
int vert0, vert1;
while(cin>>num_vertices && num_vertices!=0) {
cin>>num_edges;
//clear graph
for(int i=0; i<num_vertices; i++)
for(int j=0; j<num_vertices; j++)
graph[i][j]=false;
for(int i=0; i<num_edges; i++) {
cin>>vert0>>vert1;
graph[vert0][vert1]=graph[vert1][vert0]=true;
}
if(colorGraph()==false)
cout<<"NOT BICOLORABLE"<<endl;
else
cout<<"BICOLORABLE"<<endl;

}

return 0;
}
jaredjohnson
New poster

Posts: 11
Joined: Sun Jan 30, 2005 10:21 pm

### anybody? anybody? n/t

Still can't find the error....
jaredjohnson
New poster

Posts: 11
Joined: Sun Jan 30, 2005 10:21 pm

I think the job of this problem is: to find if there is a circle(a path from one node to itself) of odd edges.

Yile
New poster

Posts: 17
Joined: Sun Feb 27, 2005 10:36 am
Location: China

Jared Johnson's algorithm is perfectly correct. The program gets WA, because it does not print periods at the end of line.

Replace the code
Code: Select all
`if(colorGraph()==false)  cout<<"NOT BICOLORABLE"<<endl;else  cout<<"BICOLORABLE"<<endl; `

by
Code: Select all
`if(colorGraph()==false)  cout<<"NOT BICOLORABLE."<<endl;else  cout<<"BICOLORABLE."<<endl; `
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

### Thank You

You kick ass. Saved me a lot of time.

Thank You,
-Jared
jaredjohnson
New poster

Posts: 11
Joined: Sun Jan 30, 2005 10:21 pm

### 10004 W/A again, again, and again!!!

I get W/A so many times and I still can't find the bug(s), could anyone please help me??

Here is the program, written in C.
I use a silly approach, which may quite waste memory and it is rather complex, but I think it is correct. I have tried the case of disconnect graph, but the program works OK (In fact my program ignores those seperated nodes) . I really don't know why the algorithm is wrong.

--------------------------------------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>

#define TRUE 1
#define FALSE 0

int main()
{

int vertex;
int edge;
int i, j;
int v1, v2;
int connect[200][200]; //store the connecting info of two adjcent vertice
int *ColorOfNode=NULL;
int bicolorable = TRUE;

while (scanf("%d", &vertex) && vertex!=0)
{
count=0;

/* initialize connect array */
for(i=0; i<200;i++)
{
for (j=0; j<200; j++)
{
if (connect[i][j])
connect[i][j]=0;
}
}

scanf("%d",&edge);
ColorOfNode = malloc(sizeof(int)*vertex); /* dymanic allocate array to store node's color */
for(i=0;i<vertex;i++){ /* initialize ColorOfNode array, 0 means the vertex is not yet colored */
ColorOfNode[i]=0;

}

/* add connection info between nodes in the connect array */
for (i=0; i< edge; i++)
{
scanf("%d %d", &v1, &v2);
connect[v1][v2] +=1; /*this indicate the number of edges between two vertice*/
connect[v2][v1] +=1;

/* Color the vertex with two colors at the same time */
if(ColorOfNode[v1]==0 && ColorOfNode[v2]==0)
{
ColorOfNode[v1] = 1;
ColorOfNode[v2] = 2;
}
if(ColorOfNode[v1]>0 && ColorOfNode[v2]==0)
{
if(ColorOfNode[v1]==1)
ColorOfNode[v2]=2;
else
ColorOfNode[v2]=1;
}
if(ColorOfNode[v1]==0 && ColorOfNode[v2]>0)
{
if(ColorOfNode[v2]==1)
ColorOfNode[v1]=2;
else
ColorOfNode[v1]=1;
}
}

for(i=0;i<vertex;i++)
{
for(j=0;j<vertex;j++)
{

if(i!=j && connect[i][j]>0 && ColorOfNode[i]==ColorOfNode[j] )
bicolorable = FALSE; // two nodes with the same color, the graph is not bicolorable

}
}

/* output */
if(bicolorable)
printf("BICOLORABLE.\n");
else
printf("NOT BICOLORABLE.\n");

free(ColorOfNode);
bicolorable = TRUE; //reset
}

return 0;
}
Wilma
Wing Man, Leung
New poster

Posts: 1
Joined: Wed Jul 27, 2005 5:59 am
Location: Hong Kong, China

thanks i used dfs and now got AC.
Last edited by tanvir on Sat Sep 17, 2005 8:16 am, edited 1 time in total.
tanvir
New poster

Posts: 22
Joined: Wed Aug 31, 2005 12:09 pm

I think there are some things missing in your code.
First you just insert the edge from input[i][0] to input[i][1] and not the backedge. In the problemstatement its clearly said that we have nondirectional edges.
Another thing is that you go through the nodes by there number. You should do a DFS (or BFS) in this task, so you should work on the nodes when you find them, not in the ranking of there number. You can use a stack for solving this problem.
Last thing is that i am not sure with these lines:
j++;

I think, but i am not very familiar with C, that you write two times on the same position in the array, so your edge is deleted. Second thing is that you search for first -1 in the adj field, but when you found it you Increment j so you are behind the first -1 and the edge wont be find.

GeorgeBusch
New poster

Posts: 10
Joined: Fri Jun 10, 2005 5:30 pm

### 10004 Bicoloring wa

hello, every1, this is my first time posting, im having problem with this problem, i keep getting wa even tho i passed the sample test, can some1 help thx!
nvm i got it thx
rainwalkerc
New poster

Posts: 1
Joined: Fri Nov 25, 2005 8:20 am

PreviousNext

### Who is online

Users browsing this forum: No registered users and 0 guests