HDU-1213 How Many Tables

 1 #include <bits/stdc++.h>
 2 #define pb push_back
 3 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
 4 #define INF 0x3f3f3f3f
 5 #define sz size()
 6 
 7 using namespace std;
 8 typedef long long ll;
 9 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
10 const int maxn = 50003;
11 int par[maxn]; //父亲 
12 int high[maxn]; //树的高度
13 int n;
14 void init(int n)
15 {
16     _for(i,0,n)
17     {
18         par[i] = i;
19         high[i] = 0;
20     }
21 } 
22 
23 int find(int x)
24 {
25     return par[x] == x ? x : par[x] = find(par[x]);
26 }
27 
28 void unite(int x,int y)
29 {
30     x = find(x);y = find(y);
31     if(x==y) return ;
32     n --;
33     if(high[x]<high[y])
34         par[x] = y;
35     else
36     {
37         par[y] = x;
38         if(high[x]==high[y])
39             high[x] ++;
40     }
41 }
42 
43 bool same(int x,int y)
44 {
45     return find(x) == find(y); 
46 }
47 
48 
49 int main()
50 {
51     int T; 
52     scanf("%d",&T);
53     while(T--)
54     {
55         int N,M;
56         scanf("%d %d",&N,&M);
57         n = N;
58         init(N+1);
59         while(M--)
60         {
61             int a,b;
62             scanf("%d %d",&a,&b);
63             unite(a,b);
64         }
65         cout << n <<endl;
66     }
67     return 0;
68 }