10004 - Bicoloring

[Tanu]

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]

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]

i have checked out the bug!.i didn't initiate the array of disclosed in the loop.

[douzi0108]

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]

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 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[200];
        if(backtrack(colored, 0))
            cout <<  "BICOLORABLE." << endl;
        else
            cout <<  "NOT BICOLORABLE." << endl;
    }
}


Thank You,
Himanshu.

[sumantbhardvaj]

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


[rio]

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]

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]

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

[albet_januar]

Code: Select all

Acc after I use DFS


I REALLY CONFUSE BOUT THIS PROBLEM..
I THINK IT'S ONLY USE BFS..
am i wrong??

[Itachi-Forsaken]

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


[albet_januar]

is a dfs probleM??

[Ron]

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]

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

[rio]

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