HDU-1232-畅通工程(并查集)

 1 /*
 2     Name:HDU-1232-畅通工程
 3     Copyright:
 4     Author:
 5     Date: 2018/4/12 15:38:11
 6     Description:
 7     并查集模板题 
 8 */
 9 #include <iostream>
10 #include <vector>
11 #include <algorithm>
12 using namespace std;
13 struct DisjoinSet {
14     vector<int> father, rank;
15     
16     DisjoinSet(int n): father(n), rank(n) {
17         for (int i=0; i<n; i++) {
18             father[i] = i;
19         }
20     }
21     
22     int find(int v) {
23         return father[v] = father[v] == v? v:find(father[v]);
24     }
25     
26     void merge(int x, int y) {
27         int a = find(x), b = find(y);
28         if (rank[a] < rank[b]) {
29             father[a] = b;
30         } else {
31             father[b] = a;
32             if (rank[b] == rank[a]) {
33                 ++rank[a];
34             }
35         }
36     }
37 } ; 
38 int main()
39 {
40     int n, m;
41     while (cin>>n>>m)  {
42         DisjoinSet msf(1000+5);
43         for (int i=0; i<m; i++) {
44             int a,b;
45             cin>>a>>b;
46             msf.merge(a,b);
47         }
48         int ans = 0;
49         for(int i=1; i<=n; i++){
50             if(msf.father[i]==i) ans++;
51         }
52         cout<<ans-1<<endl;
53     }
54     return 0;
55 }