Stuck in Spoj's A Bug's Life for 2 days

Правка en1, от invisible_guest, 2020-07-24 22:13:07

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]; vectorv[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++;

}

}

Теги #dfs, #bipartite, #graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский invisible_guest 2020-07-24 22:17:31 4 Tiny change: 'UGLIFE/)\n```\n#in' -> 'UGLIFE/)\n\n\n```\n#in'
en3 Английский invisible_guest 2020-07-24 22:17:06 54
en2 Английский invisible_guest 2020-07-24 22:14:04 12
en1 Английский invisible_guest 2020-07-24 22:13:07 1986 Initial revision (published)