题目： 在社交网络平台注册时，用户通常会输入自己的兴趣爱好，以便找到和自己兴趣相投的朋友。有部分兴趣相同的人们就形成了“社交集群”。现请你编写程序，找出所有的集群。
输入格式： 输入的第一行给出正整数N（<=1000），即社交网络中的用户总数（则用户从1到N编号）。随后N行，每行按下列格式列出每个人的兴趣爱好： Ki: hi[1] hi[2] … hi[Ki]
输出格式： 首先在第一行输出整个网络中集群的数量，然后在第二行按非递增的顺序输出每个集群中用户的数量。数字间以1个空格分隔，行首尾不得有多余空格。
题解： 利用并查集将各个爱好团体归类，最后在一次遍历，汇总各个团体的总人数。
代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> using namespace std ; #define MAX 1005 int p[MAX] ,visit[MAX]={0} , ans[MAX] ={0}; int Find(int x) { while(x != p[x]) x = p[x]; return x; } int join(int x , int y) { int t1 = Find(x) ; int t2 = Find(y) ; if(t1 != t2) { if(t1 < t2) p[t2] = t1 ; else p[t1] = t2 ; } } bool comp(int a , int b) { return a > b ; } int main() { int n , k , h1 , h; scanf("%d" , &n); for(int i = 0 ; i < MAX ; i ++) p[i] = i ; for(int i = 0 ; i < n ; i ++) { scanf("%d: %d",&k,&h1); if(k>1) { for(int i = 2 ; i <= k ; i ++) { scanf("%d" , &h) ; join(h1 , h) ; } } visit[Find(h1)] ++ ; } int cnt = 0; for(int i = 0 ; i < MAX ; i ++) { if(visit[i]!=0) { int temp = Find(i) ; if(i != temp) { visit[temp] += visit[i] ; visit[i] = 0 ; } else cnt ++ ; } } sort(visit,visit+MAX,comp) ; printf("%d\n" , cnt) ; for(int i = 0 ; i < cnt ; i ++) { if(i == cnt -1) printf("%d\n" , visit[i]); else printf("%d " , visit[i]); } return 0 ; }