团体程序设计天梯赛
L3-003 社交集群
这是一道典型的并查集。经典的并查集所使用到的数据结构有：数组myFather，用于存储节点的父节点；函数findAnc，用于寻找节点最早的祖先节点；函数unionSet，用于结合两个集合；数组isRoot，用于统计集合的个数，以及各个集合中元素的个数。
对于本题，还使用了数组interestRoot，用于记录最早出现某兴趣的人对应的序号。合并集合的过程是：将人的最早祖先节点的父节点置为要加入的兴趣数组元素的最早祖先节点。
isRoot[i]表示编号i的人是不是它自己社交圈子的根结点，如果等于0，表示不是根结点；如果不等于0，每次标记isRoot[findAnc(i)]++，那么isRoot保存的就是：如果当前是根结点，那么这个社交圈里的总人数。
// findAnc, unionSet, myFather, isRoot
#include <bits/stdc++.h>
using namespace std;
vector<int> myFather;
vector<int> interestRoot(1001);
vector<int> isRoot; // 用于判断根节点，如果是，存储的是集合的元素个数
int findAnc(int node){
if(myFather[node] == node) return node;
else return findAnc(myFather[node]);
}
void unionSet(int a, int b){
int ancA = findAnc(a);
int ancB = findAnc(b);
myFather[ancA] = ancB;
}
bool cmp(int a, int b){ return a > b; }
int main(){
int n;
cin >> n;
myFather.resize(n + 1);
isRoot.resize(n + 1);
for(int i = 1; i <= n; i++) myFather[i] = i;
for(int i = 1; i <= n; i++){
int k;
cin >> k;
getchar();
for(int j = 0; j <= k - 1; j++){
int interest;
cin >> interest;
if(interestRoot[interest] == 0) interestRoot[interest] = i;
unionSet(i, interestRoot[interest]);
}
}
for(int i = 1; i <= n; i++) isRoot[findAnc(i)]++; // 统计每个集合中元素个数
int cnt = 0;
for(int i = 1; i <= n; i++) if(isRoot[i] != 0) cnt++;
sort(isRoot.begin(), isRoot.end(), cmp);
cout << cnt << endl;
for(int i = 0; i <= cnt - 1; i++) cout << isRoot[i] << " \n"[i == (cnt - 1)];
return 0;
}