invisible_guest's blog

By invisible_guest, history, 4 years ago, In English

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! Problem Link

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

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it