How Many Tables

题意

有N个朋友一起来吃饭，认识的人只跟认识的做一桌，认识的人是可以传递的，A认识B，B认识C，那么A就认识C，问最少需要多少张桌子？

分析

使用并查集模板套一下，最后fa[i] == i的就是一桌，计数器+1即可

AC代码

#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3+10;

int T,N,M;
int fa[maxn];
void init(){
    for(int i = 1;i<=N;i++) fa[i] = i;
}
int find(int x){
    if(x != fa[x])
        fa[x] = find(fa[x]);
    return fa[x];
}
void join(int x,int y){
    int fx = find(x),fy = find(y);
    if(fx != fy){
        fa[fx] = fy;
    }
}
int main(){
    cin>>T;
    while(T--){
        scanf("%d%d",&N,&M);
        init();
        int a,b;
        while(M--){
            scanf("%d%d",&a,&b);
            join(a,b);
        }
        for(int i = 1;i<=N;i++) find(i);
        int res = 0;
        for(int i = 1;i<=N;i++) if(fa[i] == i) res++;
        printf("%d\n",res);
    }
    return 0;
}