10004 - Bicoloring

[Sajid]

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.

[Doom_Gaze]

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.

[murtaza]

Isn't the algm. just to check if the graph is a bipartite graph or not ... i.e if there are no odd cycles ????

[jeu blanc]

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;
}

[jagadish]

Your approach is wrong ..
Use the Search link above to check the pervious posts of the problem before posting..

[Yile]

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.

[jaredjohnson]

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]

Still can't find the error....

[Yile]

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.

[mf]

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;

[jaredjohnson]

You kick ass. Saved me a lot of time.

Thank You,
-Jared

[Wing Man, Leung]

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;
}

[tanvir]

thanks i used dfs and now got AC.

[GeorgeBusch]

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:

while(adj[ input[t][0] ][j]!=-1)
j++;
adj[ input[t][0] ][j++]=input[t][1];
adj[ input[t][0] ][j]=-1;

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.

I hope I could help you a little bit

[rainwalkerc]

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