## 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

GeorgeBusch
New poster
Posts: 10
Joined: Fri Jun 10, 2005 5:30 pm
I think there are some things missing in your code.
First you just insert the edge from input to input 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] ][j]!=-1)
j++;
adj[ input[t] ][j++]=input[t];
adj[ input[t] ][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
New poster
Posts: 1
Joined: Fri Nov 25, 2005 8:20 am

### 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

Tanu
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars

### Welcome

Welcome to all new commers .... BFS or DFS or simple recurrence anyone can do it just use the color=step%2;
Is :the preveous color is ok then return and carry on..
Else :not bicolorable
Good Luck...

littlebird
New poster
Posts: 2
Joined: Fri Dec 02, 2005 3:45 pm

### 10004 puzzled!

when 10004 done,i meet a strange question: when i try several input/output myself ,it do the right thing,but in the online-judge,receive WA,but i don't know why.would anybody help me ?thank you very much!
my idea is DFS,every expanded node's color is opposite to the father's(implemented by using variable color_set).Here is my code:

Code: Select all

``````#include<iostream>
using namespace std;
bool DFS(int i);
bool check(int i);
bool graph;
int nvertice,nedge;
bool color_set=0;
bool disclosed;
bool color;
int main()
{
bool flag=0;
int i,j;
int k=0;
while(cin>>nvertice){
if(!nvertice) return 0;
for(i=0;i<200;i++) for(j=0;j<200;j++) graph[i][j]=0;
cin>>nedge;
while(k<nedge){ cin>>i>>j;graph[i][j]=1;graph[j][i]=1;k++;}
for(k=0;k<nvertice;k++){
if(!disclosed[k]) if(!DFS(k)) {cout<<"NOT BICOLORABLE."<<endl;flag=1;break;}
}
if(!flag) cout<<"BICOLORABLE."<<endl;flag=0;k=0;
}
return 0;
}
bool DFS(int i)
{
int k;
disclosed[i]=1;
color[i]=color_set;
if(!check(i))return 0;
for(k=0;k<nvertice;k++)
if(graph[i][k]&&!disclosed[k]){color_set=1-color[i];if(!DFS(k)) return 0;}

return 1;
}
bool check(int i)
{
int B={0,0};
for(int j=0;j<nvertice;j++) if(graph[i][j]&&disclosed[j])B[color[j]]++;
if(B[color[i]])return 0;
return 1;
}
``````

littlebird
New poster
Posts: 2
Joined: Fri Dec 02, 2005 3:45 pm
i have checked out the bug!.i didn't initiate the array of disclosed in the loop.

douzi0108
New poster
Posts: 2
Joined: Sun Oct 01, 2006 7:13 pm

### i have 10004 WA and i really dunno how to do it

hi, i really need help. i've checked my program against some test cases and they're rite. but when i submit, i get WA! i really dunno how to further debug cus i dun even know wats the mistake.

Code: Select all

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

class Main {
// flag used to check for non-bicolorable.
// 1 = bicolorable. 0 = non-bicolorable
int bicolorFlag = 1;

// # of edges, # of vertices
int e = 0, v = 0;

// color code used in colorVertice[]
int black = 1, red = 2;

// this matrix shows link between vertices
int vertice[][];
// this array shows the color of each vertice
int colorVertice[];

StringTokenizer st;

public static void main(String args[]) {
Main ms = new Main();
ms.setUpGraph();
}

// set up graph based on number of edges and vertices
void setUpGraph() {
String temp;

if((temp = Main.readLn(255)) != null) {
v = Integer.parseInt(temp);
}

// check if vertice = 0
if(v == 0) {
//normal termination
System.exit(0);
}
else {
if((temp = Main.readLn(255)) != null) {
e = Integer.parseInt(temp);
}
}

vertice = new int[v][v];
colorVertice = new int[v];

// pair of vertices tt are linked
int v1, v2;

// picks one vertice to be e first node.
int firstNode = 0;
boolean firstNodePicked = false;

for(int i=0; i<e; i++) {
if((temp = Main.readLn(255)) != null) {
st = new StringTokenizer(temp);
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
if(firstNodePicked == false) {
firstNode = v1;
firstNodePicked = true;
}

// 1 to indicate there's an edge between these 2 vertices
vertice[v1][v2] = 1;
vertice[v2][v1] = 1;
}
}

// start color process of graph
colorGraph(firstNode);

if(bicolorFlag == 0) {
System.out.println("NOT BICOLORABLE.");
}
else if(bicolorFlag == 1) {
System.out.println("BICOLORABLE.");
}

setUpGraph();
}

// colors the first node(0) first
void colorGraph(int first) {
// if first node is not colored, color it red
if(colorVertice[first] == 0) {
colorVertice[first] = red;
}

colorChild(first);
}

// color the child of the curr parent node
void colorChild(int currParent) {
for(int currChild=0; currChild<v; currChild++){
// if not pointing to itself
// there's edge between currChild and currParent
// currChild has color like parent (indicates non-bicolorable)
if(vertice[currChild][currParent] != vertice[currParent][currParent]
&& vertice[currChild][currParent] == 1
&& colorVertice[currChild] == colorVertice[currParent]) {
// set the flag
bicolorFlag = 0;

// will break out of for loop
break;
}

// if not pointing to itself
// there's edge between currChild and currParent
// currChild has not been colored before
else if(vertice[currChild][currParent] != vertice[currParent][currParent]
&& vertice[currChild][currParent] == 1
&& colorVertice[currChild] == 0) {
//alternate the colors between parent and child
if(colorVertice[currParent] == red)
colorVertice[currChild] = black;
else
colorVertice[currChild] = red;

// set the flag
bicolorFlag = 1;
}
}

// only if suits bicolorable criteria
// and curr vertice still within given # of vertices
if(bicolorFlag == 1 && currParent+1 < v) {
colorChild(currParent+1);
}
}

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

himanshu
New poster
Posts: 17
Joined: Mon May 15, 2006 12:24 pm
Location: Hyderabad, India
Contact:

### 10004 WA

Hi,

My code works on the sample input and also the test cases supplied in this board for this problem. I don't think I need an explicit DFS. Kindly help:-

Code: Select all

``````#include<iostream>

int G; // graph's adjacency matrix

int n; // nodes

bool valid(int k, int color, int colored[])
{
for(int v = 0; v < k; v++)
if(G[v][k] && colored[v] == color)
return false;

return true;
}

bool backtrack(int colored[], int k)

for(int color = 0; color < 2; color++)
if(valid(k, color, colored))
{
colored[k] = color;
if(k == n-1)
{
return true;
}
else
return backtrack(colored, k+1);
}
return false;
}

int main()
{
while(cin >> n)
{
for(int i = 0; i < 200; i++)
for(int j = 0; j < 200; j++)
G[i][j] = 0;
if(n == 0)
break;

int l; // edges
cin >> l;

for(int i = 0; i < l; i++)
{
int u, v; // source and target vertex
cin >> u >> v;
G[u][v] = 1;
G[v][u] = 1;
}
int colored;
if(backtrack(colored, 0))
cout <<  "BICOLORABLE." << endl;
else
cout <<  "NOT BICOLORABLE." << endl;
}
}
``````
Thank You,
Himanshu.

sumantbhardvaj
New poster
Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm
Contact:

### 10004 WA

earlier I solved this problem using a different approach but this time i tried to use Floyd warshall algorithm to solve it..
Using FY , i tried to find cycles in it of length 3.

ie. if i is connected to j and if i is also connected to k and k is connected to j then its Not Bicolrable.

But my code is surprisingly givng wrong answer.

what is the problem.

Code: Select all

``````#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int g;

class sumant
{
public:
int n,l;
int input()
{
int x,y;

cin>>n;
while(n!=0)
{
cin>>l;
for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) g[i][j]=0;

for(int i=0;i<l;i++)
{
cin>>x>>y;
g[x][y]=1;
g[y][x]=1;
}
bool p=doit();
if(p)
cout<<"BICOLORABLE.\n";
else
cout<<"NOT BICOLORABLE.\n";
cin>>n;
}

}

bool doit()
{
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(g[i][j]==1 && g[i][k]==1 && g[k][j]==1)
return false;
}
}
}
return true;
}
};
int main()
{
sumant s;
s.input();
return 0;
}
``````

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
It's a interesting approach, but wrong.

Think what will happen if thers is a cycle of length 5 or more.
You must consider all odd length cycle.

Heres the simple test case that your approach doesn't work.

Code: Select all

``````5
5
0 1
1 2
2 3
3 4
4 0
0
``````
ADD : Don't open a new thread if there is already a thread for the problem.

sumantbhardvaj
New poster
Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm
Contact:
Yeah thanx rio ,

I got the error , Now i m puzzled how can i use Floyd Warshall to find cylces of odd length ?

I mean is it useful to apply FY here. Plz throws some light

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
I have no idea finding odd length cycle with Floyd Warshall.

albet_januar
New poster
Posts: 35
Joined: Wed Apr 12, 2006 6:03 pm
Location: jakarta, indonesia
Contact:

### 10004 - Bicoloring

Code: Select all

``````Acc after I use DFS
``````
I REALLY CONFUSE BOUT THIS PROBLEM..
I THINK IT'S ONLY USE BFS..
am i wrong??
Last edited by albet_januar on Mon Jun 04, 2007 6:21 pm, edited 1 time in total.

Itachi-Forsaken
New poster
Posts: 10
Joined: Mon May 07, 2007 4:45 am
Hi

I attempted this problem by using bfs, and check that if two nodes on the same level had an edge to each other, it would be impossible

Can someone tell me if there is something wrong with my algorithm?

Thanks

Here is my code

Code: Select all

``````#include<iostream>

#define MAXV 200
#define MAXD 200

using namespace std;

class graph
{
private:
int levels[MAXV][MAXV], level_index[MAXV], maxlvl;
int coloured[MAXV];
public:
int edges[MAXV][MAXD];
int degrees[MAXV];
int nvertices;
int nedges;
graph();
void bfs(int, int);
void check_bicolour(void);
};

graph :: graph() : nvertices(0), nedges(0), maxlvl(0)
{
int i, j;
for( i=0; i<MAXV; i++ )
{
degrees[i]=0;
level_index[i]=0;
coloured[i]=0;
for( j=0; j<MAXV; j++ )
levels[i][j]=0;
for( j=0; j<MAXD; j++ )
edges[i][j]=0;
}
}

void graph :: bfs(int n, int level)
{
if( level>maxlvl ) maxlvl=level;
if( n==0 ) coloured=1;
int kids[MAXV];
int i, j, m=0;
for( i=0; i<degrees[n]; i++ )
{
j=edges[n][i];
if( coloured[j]==0 )
{
coloured[j]=1;
levels[level+1][level_index[level+1]++]=j;
kids[m++]=j;
}
}
for( i=0; i<m; i++ )
bfs(kids[i], level+1);
}

void graph :: check_bicolour(void)
{
int i, j, k, l;
for( i=1; i<=maxlvl; i++ )
{
for( j=0; j<level_index[i]-1; j++ )
{
for( k=j+1; k<level_index[i]; k++ )
{
for( l=0; l<degrees[levels[i][j]]; l++)
{
if( edges[levels[i][j]][l]==levels[i][k] )
{
cout<<"NOT BICOLORABLE."<<endl;
return;
}
}
}
}
}

cout<<"BICOLORABLE."<<endl;
}
int main()
{
while(1)
{
graph g;

//input
cin>>g.nvertices;
if( g.nvertices==0 ) break;
cin>>g.nedges;
int i;
for( i=0; i<g.nedges; i++ )
{
int a, b;
cin>>a>>b;
g.edges[a][g.degrees[a]++]=b;
g.edges[b][g.degrees[b]++]=a;
}

g.bfs(0, 0);
g.check_bicolour();
}

return 0;
}
``````

albet_januar
New poster
Posts: 35
Joined: Wed Apr 12, 2006 6:03 pm
Location: jakarta, indonesia
Contact:
is a dfs probleM??

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

### My different program

i checked my program by many input cases.......still i am getting wrong answer.
Please check my program and verify with input cases . And tell me for what input cases my program is wrong........
My program is given below..

#include<iostream>
#include<vector>
using namespace std;
int main(){
int n,a,b,k;
long long int l;
vector<int> v,w1,w2;
while(cin>>n){
if(n==0) exit(0);
for(k=0;k<n;k++) v.push_back(0);
cin>>l;
while(l--){
cin>>a>>b;
if(a>b){
k=a;
a=b;
b=k;
}
w1.push_back(a);
w2.push_back(b);
}
for(k=1;k<w1.size();k++){
a=w1[k];
b=w2[k];
for(l=k-1;l>=0;l--){
if(w1[l]<=a) break;
w1[l+1]=w1[l];
w2[l+1]=w2[l];
}
w1[l+1]=a;
w2[l+1]=b;
}
k=0;
for(l=0;l<w1.size()&&k==0;l++){
a=w1[l];
b=w2[l];
if(v[a]==0||v==0){
if(v[a]==0&&v==0){
v[a]=1;
v=2;
}
else if(v[a]==0) v[a]=3-v;
else v=3-v[a];
}
else{
if(v[a]==v) k=1;
}
}
if(k==1) cout<<"NOT BICOLORABLE."<<endl;
else cout<<"BICOLORABLE."<<endl;
v.resize(0);
w1.resize(0);
w2.resize(0);
}
return 0;
}