## 10004 - Bicoloring

Moderator: Board moderators

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

Tanu
Learning poster

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

### 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[200][200];int nvertice,nedge;bool color_set=0;bool disclosed[200];bool color[200];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[2]={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.
littlebird
New poster

Posts: 2
Joined: Fri Dec 02, 2005 3:45 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)); } }`
douzi0108
New poster

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

### 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[200][200]; // graph's adjacency matrixint n; // nodesbool 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[200];        if(backtrack(colored, 0))            cout <<  "BICOLORABLE." << endl;        else            cout <<  "NOT BICOLORABLE." << endl;    }}`

Thank You,
Himanshu.
himanshu
New poster

Posts: 17
Joined: Mon May 15, 2006 12:24 pm

### 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[205][205];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;}`
sumantbhardvaj
New poster

Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm

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
`550 11 22 33 44 00`

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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
sumantbhardvaj
New poster

Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm

I have no idea finding odd length cycle with Floyd Warshall.

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

### 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.
albet_januar
New poster

Posts: 35
Joined: Wed Apr 12, 2006 6:03 pm
Location: jakarta, indonesia

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 200using 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[0]=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;}`
Itachi-Forsaken
New poster

Posts: 10
Joined: Mon May 07, 2007 4:45 am

is a dfs probleM??
albet_januar
New poster

Posts: 35
Joined: Wed Apr 12, 2006 6:03 pm
Location: jakarta, indonesia

### 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[b]==0){
if(v[a]==0&&v[b]==0){
v[a]=1;
v[b]=2;
}
else if(v[a]==0) v[a]=3-v[b];
else v[b]=3-v[a];
}
else{
if(v[a]==v[b]) k=1;
}
}
if(k==1) cout<<"NOT BICOLORABLE."<<endl;
else cout<<"BICOLORABLE."<<endl;
v.resize(0);
w1.resize(0);
w2.resize(0);
}
return 0;
}
Ron
Learning poster

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

please !! check the above program , and reply me any test cases , for what my program is wrong.............
Ron
Learning poster

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

I can't understand your program well. Could you give a brief explanation of you algorithm ?
Then it well be much more easier to understand and debug.

EDIT : When you post your code, use Code tags.

EDIT : OK. I understood your algorithm. Actually its not correct. I'll make a critical test case.
----
Rio

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

PreviousNext