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.

[md6nguyen]

Hi I'm trying to solve problem 10004 using Java but got this error:

gcj: Internal compiler error: program jc1 got fatal signal 11

Looks like this is not syntax error but the compiler has crashed or something. Anyone know what's going on? Here is the source code

import java.util.*;
import java.io.*;

class Main {

static void main(String args[]) {
int nVertices;
int nEdges;
int i;
final int maxLg = 255;
Main g;
String s;
StringTokenizer st;

String color[] = new String[Main.maxNumVertices];

while (true) {

st = new StringTokenizer(readLn(maxLg));
nVertices = Integer.parseInt(st.nextToken());
if (nVertices == 0) return;

st = new StringTokenizer(readLn(maxLg));
nEdges = Integer.parseInt(st.nextToken());

g = new Main(nVertices, nEdges);

for (i = 0; i < nEdges; i++) {
st = new StringTokenizer(readLn(maxLg));
g.insertEdge(Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()));
}

if (g.isBicolorable(color)) {
System.out.println("BICOLORABLE");
}
else {
System.out.println("NOT BICOLORABLE");
}
}
}

static final int maxNumVertices = 200;
int nVertices;
int nEdges;
Vector edges[] = new Vector[maxNumVertices];

Main(int nv, int ne) {
nVertices = nv;
nEdges = ne;
for (int i=0; i<maxNumVertices; i++) {
edges = new Vector(maxNumVertices/10);
}
}

void insertEdge(int x, int y) {
edges[x].addElement(new Integer(y));
edges[y].addElement(new Integer(x));
}

/* Determine if the graph is bicolorable
* using Breadth-First Search
* Assume that the graph is connected
*/
boolean isBicolorable(String color[]) {
Vector q;
int i;
int e;
int v;
final String RED = new String("RED");
final String BLACK = new String("BLACK");
String nextColor = RED;

for (i = 0; i < nVertices; i++) {
color = null;
}

q = new Vector(nVertices);
q.addElement(new Integer(0));
color[0] = RED;

while (q.isEmpty() == false) {
v = ((Integer) q.firstElement()).intValue();
q.removeElementAt(0);
nextColor = color[v] == RED ? BLACK : RED;
for (i = 0; i < edges[v].size(); i++) {
e = ((Integer) edges[v].elementAt(i)).intValue();
if (color[e] == null) {
color[e] = nextColor;
q.addElement(new Integer(e));
}
else if (color[e] != nextColor) {
return false;
}
}
}

return true;
}

static String readLn(int maxLg) {
byte lin[] = new byte[maxLg];
int lg = 0, car = -1;
String line = "";

try {
while (lg < maxLg) {
car = System.in.read();
if (car<0 || car=='\n') break;
lin[lg++] += car;
}
}
catch (IOException e) {return null;}

if (car<0 && lg==0) return null;
return (new String(lin, 0, lg));
}
}


[java][/java]

[Spike]

This compile error is given by the judge when you try using a function that isn't recognized by their compiler. Sure enough, your code compiles fine using the standard java compiler, but the judge's Java support sucks. Note to judge: Quit upgrading your Pascal compiler and support some real java already, the ACM does.

I've looked through your code and have done many submissions to the UVA site. It appears that your problem is in this line:

Code: Select all

e = ((Integer) edges[v].elementAt(i)).intValue();

An aside... this is an inefficient way to go about solving the problem. Just run Warshall's algorithm on a boolean array of nodes, like so...

if ( connects[ a ][ b ] & connects[ b ][ c ] & connects[ a ][ c ] ) we have a problem.

So instead of updating your nodes, check to see if it can be updated. If it can and it's already true, then it's not bicolorable.

[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[j] = 0;
}
}

for (i = 0; i < 200; i++) {
nodeColor = 0;
nodeInvolved = 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 == 1) {
for (j = 0; j < 200; j++) {
if (nodeConnections[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) {
for (j = 0; j < 200; j++) {
if (nodeConnections[j]) {
if (nodeColor == 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]) {
if(color==3) {
if(!dfs(i, 1-c))
return false;
}
else if(color==c) {
return false;
}
}

return return_value;
}


bool colorGraph() {
for(int i=0; i<num_vertices; i++)
color = 3;
for(int i=0; i<num_vertices; i++)
if(color == 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[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[j])
connect[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=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[j]>0 && ColorOfNode==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.