Udbhav Govil Udbhav Govil - 2 months ago 21
C++ Question

How to check the graph is 2-colorable or not?

I want to find whether the graph is 2-colorable or not more ie. bipartite or non-bipartite.

Here is my code in C++ I'm using Welsh Powell Algorithm but something is wrong in the code may be I am missing some corner cases or some logical mistake.

Input n=no. of vertex, m = no. of edges, 0 based indexing

#include <iostream>
#include <algorithm>
using namespace std;


pair <int,int> s[1001];
int comp( pair <int,int> s1, pair <int,int> s2)
{
if(s1.first>s2.first)
return 0;
else
return 1;
}
int main()
{

int n,i,j,k,flag=0;
bool a[1001][1001]={false};
int s1[1001]={0};
int s3[1001]={0};
for(i=0;i<1001;i++)
{
s[i].first=0;
s[i].second=i;
//s1[i]=0;
}
long long m;
cin>>n>>m;
while(m--)
{
int x,y;
cin>>x>>y;
if(x==y)
continue;
a[x][y]=true;
a[y][x]=true;
}

for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a[i][j]==true )
s[i].first++;

sort(s,s+n,comp);
int color=1,p=0,z,f;

for(i=0;i<n;i++)
{
k = s[n-i-1].second;
if(s1[k]==0)
{
s1[k]=color;
p=0;
s3[p++]=k;
for(j=n-1;j>=0;j--)
{
f=0;
if(s1[s[j].second]==0)
{
for(z=0;z<p;z++)
{
if(a[s3[z]][s[j].second]==false || s3[z]==s[j].second)
continue;
else
{
f=1;
break;
}
}
if(f==1)
continue;
else
{
s3[z]=s[j].second;
p++;
s1[s[j].second]=color;
}
}
}

color++;
}
if(color==3)
break;
}
for(i=0;i<n;i++)
if(s1[i]==0)
{
flag=1;
break;
}

if(flag==1)
cout<<"NO\n";
else
cout<<"YES\n";

return 0;
}

Answer

To show that a graph is bipartite, you do not need a fancy algorithm to check. You can simply use a coloring DFS (Depth-First Search) function. It can be implemented as follows:

int color[100005];              //I assume this is the largest input size, initialise all values to -1.
vector<int> AdjList[100005];    //Store the neighbours of each vertex
bool flag = true;               //Bipartite or Not Bipartite

void dfs(int x, int p){         //Current vertex, Parent Vertex
    if (!flag) return;
    if (p == -1) color[x] = 0;
    else color[x] = 1 - color[p];
    for (int i = 0; i < AdjList[x].size(); ++i){      //For Every Neighbour
        int v = AdjList[x][i];                        //Vertex to be checked
        if (color[v] == color[x]){                    //Same color -> Not bipartite
            flag = false;
            return;
        }      
        if (color[v] == -1){                           //Unchecked
            dfs(v,x);                                  //color
        }              
    }
}