HDU 1272 小希的迷宫

(1) 判断是否有回路，这个可以用并查集来做，一旦给定的两个节点a，b是属于同一个集合，那么便可以判定有回路

（2）看是否只有一个联通分支，这个可以用并查集来做，最终并查集只有一个根节点

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 #define MAX 100000 + 5
 6 using namespace std;
 7 
 8 int parent[MAX];
 9 bool used[MAX];
10 
11 void Make_Set(){
12     for(int i = 0; i < MAX; i ++ ) parent[i] = i;
13 }
14 
15 int Find_Set(int x){
16     return parent[x] == x ? x : (parent[x]=Find_Set(parent[x]));
17 }
18 
19 bool Union_Set(int x,int y){
20     int a = Find_Set(x), b = Find_Set(y);
21     if( a == b) return false;
22     else{
23         parent[a] = b;
24         return true;
25     }
26 }
27 
28 int main(){
29     while(1){
30         bool isExit = false, isLoop = false;
31         int a,b;
32         memset(used,false,sizeof(used));
33         Make_Set();
34         while(cin >> a >> b && a && b){
35             if(a == -1 || b == -1) {isExit  =true;break;}
36             used[a] = true; used[b] = true;
37             if(!Union_Set(a,b)) isLoop = true;
38         }
39         if(isExit) break;
40         else if(isLoop) cout<<"No"<<endl;
41         else{
42             int cnt = 0;
43             for(int i = 0 ;i < MAX; i ++ ){
44                 if(used[i] && i == Find_Set(i)) cnt++;
45             }
46             if(cnt == 1 || cnt == 0) cout<<"Yes"<<endl;
47             else cout<<"No"<<endl;
48         }
49     }
50     return 0;
51 }