题目

解决

思路

用father[N]实现并查集用hobby[N]记录第一个喜欢hobby i的人的id，其他人和第一个做并集用isRoot[N]记录第i个人作为根的并集的人数

实现

Code1

#include<cstdio> #include<algorithm> using namespace std; const int N = 1010; int father[N]; int isRoot[N] = {0}; int hobby[N] = {0}; void init(int n){ for(int i=1; i<=n; i++){ father[i] = i; } } int findFather(int x){ int a = x; while(x != father[x]){ x = father[x]; } while(a != father[a]){ int z = a; a = father[a]; father[z] = x; } return x; } void Union(int a, int b){ int faA = findFather(a); int faB = findFather(b); if(faA != faB){ father[faA] = faB; } } bool cmp(int a, int b){ return a > b; } int main(){ int n; scanf("%d", &n); init(n); int k, h; for(int i=1; i<=n; i++){ //人的id scanf("%d:", &k); for(int j=0; j<k; j++){ scanf("%d", &h); if(hobby[h] == 0){ // hobby第一次有人喜欢 hobby[h] = i; } Union(i, findFather(hobby[h])); } } for(int i=1; i<=n; i++){ isRoot[findFather(i)]++; } int ans = 0; for(int i=1; i<=n; i++){ if(isRoot[i] != 0){ ans++; } } printf("%d\n", ans); sort(isRoot+1, isRoot+n+1, cmp); for(int i=1; i<=ans; i++){ printf("%d", isRoot[i]); if(i < ans) printf(" "); } return 0; }