HDU1213 How Many Tables（并查集）

题目链接

题意：n 个人，如果 a 和 b 认识，b 和 c 认识，那么认为 a b c 都互相认识，三个人被安排在一张桌子上，问这 n 个人最少安排多少张桌子。

并查集裸题。

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

int fa[1005];
int n, m, t;
int findfa(int x){
    if(fa[x] != x){
        fa[x] = findfa(fa[x]);
    }
    return fa[x];
}

void add(int x, int y){
    if(x > y)
        swap(x, y);
    x = findfa(x);
    y = findfa(y);
    if(x != y){
        fa[y] = x;
        n--;
    }
}

int main(){
//    freopen("a.txt", "r", stdin);
    cin >> t;
    while(t--){
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i++)
            fa[i] = i;
        while(m--){
            int a, b;
            scanf("%d %d", &a, &b);
            add(a, b);
        }
        cout << n << endl;
    }
    return 0;
}