OJ Board

Posted: **Fri Sep 16, 2005 10:07 am**

I think there are some things missing in your code.
First you just insert the edge from input[0] to input[1] 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][0] ][j]!=-1)
j++;
adj[ input[t][0] ][j++]=input[t][1];
adj[ input[t][0] ][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

Posted: **Fri Nov 25, 2005 8:25 am**

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

Posted: **Tue Nov 29, 2005 2:24 pm**

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

Posted: **Fri Dec 02, 2005 4:01 pm**

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

Posted: **Sat Dec 03, 2005 5:27 am**

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

Posted: **Sun Oct 01, 2006 7:29 pm**

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

Posted: **Wed Nov 15, 2006 4:57 pm**

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.

Posted: **Thu Feb 01, 2007 10:09 am**

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

Posted: **Thu Feb 01, 2007 10:17 am**

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

ADD : Don't open a new thread if there is already a thread for the problem.

Posted: **Thu Feb 01, 2007 10:28 am**

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

Posted: **Fri Feb 02, 2007 1:20 am**

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

Posted: **Wed May 16, 2007 7:31 pm**

Code: Select all

Acc after I use DFS

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

Posted: **Tue May 22, 2007 12:32 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[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;
}

Posted: **Fri Jun 01, 2007 6:44 am**

is a dfs probleM??

Posted: **Mon Jul 23, 2007 5:12 pm**

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

OJ Board

10004 - Bicoloring

10004 Bicoloring wa

Welcome

10004 puzzled!

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

10004 WA

10004 WA

10004 - Bicoloring

My different program