http://poj.org/problem?id=2492
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #define maxn 100010 6 int p[maxn],rela[maxn]; 7 using namespace std; 8 int n,m; 9 void make() 10 { 11 for(int i=1; i<=n; i++) 12 { 13 p[i]=i; 14 rela[i]=0; 15 } 16 } 17 int find1(int x) 18 { 19 int temp=p[x]; 20 if(x==p[x]) 21 return x; 22 p[x]=find1(p[x]); 23 rela[x]=(rela[x]==rela[temp])?0:1; 24 return p[x]; 25 } 26 void unionset(int x,int y,int px,int py) 27 { 28 p[px]=p[py]; 29 rela[px]=(rela[x]==rela[y])?1:0; 30 } 31 int main() 32 { 33 int t,a,b; 34 scanf("%d",&t); 35 for(int i=1; i<=t; i++) 36 { 37 scanf("%d%d",&n,&m); 38 bool flag=false; 39 memset(rela,0,sizeof(rela)); 40 make(); 41 for(int j=0; j<m; j++) 42 { 43 scanf("%d%d",&a,&b); 44 int fa=find1(a); 45 int fb=find1(b); 46 if(!flag){ 47 if(fa==fb) 48 { 49 if(rela[a]==rela[b]) 50 { 51 flag=true; 52 } 53 } 54 else 55 unionset(a,b,fa,fb); 56 } 57 } 58 printf("Scenario #%d: ",i); 59 if(flag) 60 { 61 62 printf("Suspicious bugs found! "); 63 } 64 else 65 printf("No suspicious bugs found! "); 66 67 } 68 }