1213 How Many Tables（简单并查集）

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <limits.h> 
 5 #include <algorithm>
 6 #include <iostream>
 7 #include <ctype.h>
 8 #include <iomanip>
 9 #include <queue>
10 #include <map>
11 #include <stdlib.h>
12 using namespace std;
13 
14 int f[1010];
15 int n,m;
16 
17 void init()
18 {
19     for(int i=0;i<=n;i++)
20         f[i]=i;
21 }
22 
23 int find(int x)
24 {
25     if(x==f[x])
26         return f[x];
27     f[x]=find(f[x]);
28     return f[x];
29 }
30 
31 void Union(int x,int y)
32 {
33     int a=find(x);
34     int b=find(y);
35     if(a==b)
36         return;
37     f[a]=b;
38 }
39 
40 int main()
41 {
42     int t,a,b;
43     while(cin>>t){
44         while(t--){
45             scanf("%d %d",&n,&m);
46             init();
47             int sum=0;
48             for(int i=0;i<m;i++){
49                 scanf("%d %d",&a,&b);
50                 Union(a,b);
51             }
52             for(int i=1;i<=n;i++){
53                 if(i==find(i)){
54                     sum++;
55                 }
56             }
57             printf("%d\n",sum);
58         }
59     }
60 }