PAT1107

原题

https://pintia.cn/problem-sets/994805342720868352/exam/problems/994805361586847744?type=7&page=1

问题大意：给定n个人，每一个人都有$K_i$个兴趣，拥有相同兴趣的两个人可以算在同一个圈子里。问最后一共有多少个圈子。

思路

很显然的并查集考点。不同的两个人可以通过具有的某个相同的兴趣连接起来。具体地，下面的两个人（按照输入格式）属于同一个圈子：

2: 5 3
4: 6 8 1 5

因为他们都有一个共同的兴趣——5号。随后，下面的人也属于该圈子，因为其中均含有兴趣1号。

3: 1 2 9

因此，我们可以从兴趣的角度，设计并查集。对于给定的某个人的兴趣：

我们将它们进行合并，即$\forall j \in \{2,\dots,K_i\}, \mathrm{Union}(h_i[1], h_i[j])$，然后直接$\mathrm{father[Find(h_i[1])]++}$即可。

完整代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int father[1005];
int symbols[1005];
int res[1005];
vector<int> tmp;
int n;
void init() {
    int i;
    for(i=1; i<=1005; i++)    father[i] = i;
}

int Find(int x) {
    if(x == father[x])    return x;
    return father[x] = Find(father[x]);
}

void Union(int x, int y) {
    int px = Find(x);
    int py = Find(y);
    if(px != py) {
        father[py] = px;
    }
}

bool comp(int a, int b) {
    return a > b;
}

int main() {
    scanf("%d", &n);
    init();
    int i;
    for(i=0; i<n; i++) {
        int k, j, a;
        scanf("%d: %d", &k, &a);
        for(j=1; j<k; j++) {
            int t;
            scanf("%d", &t);
            Union(a, t);
        }
        symbols[i] = a;
    }
    for(i=0; i<n; i++) {
        res[Find(symbols[i])]++;
    }
    for(i=1; i<1005; i++) {
        if(res[i] && Find(i)==i)    tmp.push_back(res[i]);
    }
    printf("%d\n", tmp.size());
    sort(tmp.begin(), tmp.end(), comp);
    for(i=0; i<tmp.size(); i++) {
        if(i)    printf(" %d", tmp[i]);
        else    printf("%d", tmp[i]);
    }
    printf("\n");
}