HDOJ-1213 How Many Tables

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1213

题目大意

$N$个朋友参加生日派对，相互认识的坐一桌，问最少需要几张桌子。其中认识关系满足传递性。

Solution

经典的并查集问题，直接上代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
int fa[N];
int find(int x){
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tt,n,m,x,y;
    cin>>tt;
    while (tt--){
        cin>>n>>m;
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=1;i<=m;i++){
            cin>>x>>y;
            fa[find(x)]=find(y);
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(fa[i]==i) cnt++;
        }
        cout<<cnt<<'\n';
    }
}