并查集模板 hdu1703

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstdio>
 6 
 7 using namespace std;
 8 
 9 const int maxn = 2e5 + 10;
10 
11 int n, m;
12 int s[maxn];
13 int h[maxn];
14 
15 void init_set()
16 {
17     for(int i = 0 ; i <= 2*n ; i++){///caution 
18         s[i] = i;
19         h[i] = 0;
20     }
21 }
22 
23 int find(int x)
24 {
25     int now = x;
26     while(now != s[now])    now = s[now];//find root
27     int i = x;
28     int j;
29     while(i != now){
30         j = s[i];//j作为临时变量存储父亲 
31         s[i] = now;
32         i = j;//父亲变儿子,再找爷爷... 
33     }
34     return now;
35 }
36 
37 void union_set(int a, int b)
38 {
39     int p = find(a);
40     int q = find(b);
41     if(p == q)    return ;
42     
43     if(h[p] == h[q]){
44         h[p] += 1;
45         s[q] = p;
46     }else{
47         if(h[p] < h[q])    s[p] = q;
48         else    s[q] = p;
49     }
50 }
51 
52 int main(){
53     int T; cin >> T;
54     while(T--){
55         scanf("%d%d",&n,&m);
56         init_set();
57         
58         for(int i = 1 ; i <= m ; i++){
59             //char ch;
60             int a, b;
61             //scanf("
%c%d%d", &ch, &a, &b);
62             /* 
63             if(ch == 'D'){                
64                 union_set(a + n, b);
65                 union_set(a, b + n);
66             }else{
67                 if(find(a) == find(b) || find(a + n) == find(b + n)){
68                     cout << "In the same gang." << endl;
69                 }else if(find(a + n) == find(b) || find(b + n) == find(a)){
70                     cout << "In different gangs." << endl;            
71                 }else{
72                     cout << "Not sure yet." << endl;
73                 }
74             }*/ 
75         }
76         
77     }
78 
79     return 0;
80 }
注意点数字！ 2e5之神