题目链接：点击打开链接
题目大意：一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。
解题思路：并查集思路，轮到第几个人时，以它的 id 为 root，然后吸收它自己所有的兴趣爱好编号，这样就可以达到有部分兴趣爱好相同的人在一个集群里的效果。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define ssclr(ss) ss.clear(), ss.str("") #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; int pre[2009], vis[1009], cnt[2009]; void init() { for(int i=1;i<=2009;i++) pre[i]=i; } int findx(int x) { return pre[x]==x ? x : pre[x]=findx(pre[x]); } void join(int x,int y) { int fx=findx(x), fy=findx(y); if(fx!=fy) pre[fx]=fy; } int main() { init(); int n,k,t,id; scanf("%d",&n); for(int i=1;i<=n;i++) { id=1000+i; scanf("%d:",&k); while(k--) { scanf("%d",&t); join(t,id); } vis[i]=t; // 记录其中一个点即可，因为都是连结在一起的 } for(int i=1;i<=n;i++) { id=findx(vis[i]); cnt[id]++; } sort(cnt,cnt+2009,greater<int>()); int l; for(l=0;;l++) if(cnt[l]==0) break; printf("%d\n",l); for(int i=0;i<l;i++) printf("%d%c",cnt[i],i==l-1?'\n':' '); return 0; }
