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;
}

Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 并查集