i have been stuck in this problem for 2 days…Can anyone tell me what am i doing wrong just simply checking bipartite or not with dfs, tried all the cases mentioned in the comment section of spoj and all of them worked ! also noticed that graph could be dis-connected,kept all those issues in my mind while coding.still what is going wrong? Can someone help me finding the bug? Thanks!
#include<bits/stdc++.h>
using namespace std;
const int x=1e6+5;
int color[2005];
bool is_visited[2005];
vector<int>v[x];
bool flag=true;
void dfs(int a)
{
if(is_visited[a] || flag==false)
{
return;
}
is_visited[a]=true;
if(color[a]==-1)
color[a]=0;
for(auto it = v[a].begin();it!=v[a].end();it++)
{
if(color[*it]==-1)
{
if(color[a]==0)
{
color[*it]=1;
}
else
{
color[*it]=0;
}
}
else
{
if(color[*it]==color[a])
{
flag=false;
return;
}
}
if(!is_visited[*it])
{
dfs(*it);
}
}
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int t;
scanf("%d",&t);
int c=1;
while(t--)
{
int a,b;
scanf("%d %d",&a,&b);
flag =true;
fill(color,color+2005,-1);
v->clear();
while(b--)
{
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=a;i++)
{
if(!is_visited[i])
{
dfs(i);
}
}
printf("Scenario #%d:\n",c);
if(flag)
{
printf("No suspicious bugs found!\n");
}
else
{
printf("Suspicious bugs found!\n");
}
c++;
}
}