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

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

Post by 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.
Sajid Online: www.sajidonline.com

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

10004 Bicoloring

Post by 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
New poster
Posts: 2
Joined: Wed Dec 03, 2003 9:50 pm

Crashing gcj ?

Post by 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
New poster
Posts: 29
Joined: Mon Mar 18, 2002 2:00 am
Location: Washington State
Contact:

Post by 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
New poster
Posts: 7
Joined: Tue Jul 20, 2004 7:42 pm
Location: India

Post by 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 ????
Putting n programmers on a problem will not result in the time of solving the problem to reduce by n.

jeu blanc
New poster
Posts: 2
Joined: Wed Mar 23, 2005 11:41 am
Location: Germany
Contact:

10004, Bicoloring - testcases or algorithm-review?!

Post by 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;
}
One for all, and all for one!

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

Post by jagadish »

Your approach is wrong ..
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.

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

Post by 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
New poster
Posts: 11
Joined: Sun Jan 30, 2005 10:21 pm

10004

Post by 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
New poster
Posts: 11
Joined: Sun Jan 30, 2005 10:21 pm

anybody? anybody? n/t

Post by jaredjohnson »

Still can't find the error....

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

Post by 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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by 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
New poster
Posts: 11
Joined: Sun Jan 30, 2005 10:21 pm

Thank You

Post by jaredjohnson »

You kick ass. Saved me a lot of time.

Thank You,
-Jared

Wing Man, Leung
New poster
Posts: 1
Joined: Wed Jul 27, 2005 5:59 am
Location: Hong Kong, China
Contact:

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

Post by 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;
}
Wilma

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

10004 headache

Post by tanvir »

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.

Post Reply

Return to “Volume 100 (10000-10099)”