HDU-1213-How Many Tables(并查集)

 1 /*
 2     Name:HDU-1213-How Many Tables
 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 t;
41     cin>>t;
42     while (t--)  {
43         int n, m;
44         cin>>n>>m;
45         DisjoinSet msf(1000+5);
46         for (int i=0; i<m; i++) {
47             int a,b;
48             cin>>a>>b;
49             msf.merge(a,b);
50         }
51         int ans = 0;
52         for(int i=1; i<=n; i++){
53             if(msf.father[i]==i) ans++;
54         }
55         cout<<ans<<endl;
56     }
57     return 0;
58 }