HDU 1213 How Many Tables

题意：有n个人一起吃饭，有些人相互认识，有些人不认识，认识的人只想和认识的人一起吃饭，不想和

陌生人一起吃饭，问需要几张桌子。

题解：并查集

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N = 1e3+7;
 5 int t,n,m,a,b;
 6 int fa[N];
 7 //若x是树根，则x就是集合代表，否则递归访问fa[x]直至根节点
 8 int find(int x)  //查找
 9 {
10     if(x == fa[x]) return x;
11     return fa[x] = find(fa[x]);
12 }
13 //合并元素x和y所在的集合，就是让x的树根作为y的树根的子节点。
14 void Merge(int x,int y) 
15 {
16     fa[find(x)]=find(y);
17 }
18 int main()
19 {
20     scanf("%d",&t);
21     while(t--)
22     {
23         int ans = 0;
24         //设有N个元素，最初所有元素各自构成一个独立的集合。
25         for(int i=1;i<=N;i++) fa[i]=i; 
26         scanf("%d%d",&n,&m);
27         for(int i=1;i<=m;i++)
28         {
29             scanf("%d%d",&a,&b);
30             Merge(a,b);  //合并
31         }
32         for(int i=1;i<=n;i++)
33             if(fa[i]==i) ans++;
34         printf("%d
",ans);
35     }
36     return 0;
37 }