Time
Limit: 2000/1000 MS (Java/Others) Memory Limit:
65536/32768 K (Java/Others)
Total Submission(s):
23551 Accepted Submission(s):
7234
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<string> 6 #include<cmath> 7 #include<map> 8 #include<queue> 9 using namespace std; 10 const int N=100010; 11 int father[N],vis[N],flag; 12 bool mm; 13 void begin( ) 14 { 15 for(int i=0;i<=N;i++) 16 { 17 father[i]=i; 18 vis[i]=0; 19 } 20 mm=true; 21 } 22 int find(int x) 23 { 24 while(father[x]!=x) 25 { 26 x=father[x]; 27 } 28 return x; 29 } 30 void query() 31 { 32 int k=0; 33 for(int i=1;i<=N;i++) 34 if(vis[i]==1 && father[i]==i)//查询几个父亲;多于一个就不对 35 { 36 k++; 37 if(k>=2) 38 {mm=false; break;} 39 } 40 } 41 int main() 42 { 43 int x,y,px,py; 44 while(1) 45 { begin(); 46 while(scanf("%d %d",&x,&y) && x+y) 47 { 48 if(x+y<0) 49 return 0; 50 vis[x]=1;vis[y]=1; 51 px=find(x); py=find(y); 52 if(px == py) //如果两个点父亲相同,直接No,好直接啊,为什么啊,我都不懂为什么这样; 53 mm=false; 54 else father[py]=px; 55 } 56 query(); 57 if(mm) 58 printf("Yes\n"); 59 else printf("No\n"); 60 } 61 return 0; 62 }
hdoj 1272 小希的迷宫 又一个并查集的简单应用,布布扣,bubuko.com
原文:http://www.cnblogs.com/lovychen/p/3680041.html