| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
简单的并查集, 留下代码~~~~~~~#include <stdio.h> int father[100010], kind[100010]; void makeset(int n) { int i; for(i=1;i<=n;++i) { father[i]=i; kind[i]=0; } } int findset(int x) { int temp; if(x!=father[x]) { temp=father[x]; father[x]=findset(father[x]); kind[x]=(kind[x]+kind[temp])%2; } return father[x]; } void Union(int x, int y) { int xx, yy; xx=findset(x); yy=findset(y); father[yy]=xx; kind[yy]=(kind[x]-kind[y]+1)%2; } int main() { int T, N , M, ai, bi, aai, bbi, kk, tt, tag; scanf("%d", &T); for(kk=0;kk<T;++kk) { scanf("%d%d", &N, &M); makeset(N); tag=0; for(tt=0;tt<M;++tt) { scanf("%d%d",&ai, &bi); aai=findset(ai); bbi=findset(bi); if(aai!=bbi) { Union(ai, bi); } else { if(kind[bi]==kind[ai]) { tag=1; } } } if(tag==0) { printf("Scenario #%d:\n", kk+1); printf("No suspicious bugs found!\n\n"); } else { printf("Scenario #%d:\n", kk+1); printf("Suspicious bugs found!\n\n"); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator