Description:

在社交网络平台注册时，用户通常会输入自己的兴趣爱好，以便找到和自己兴趣相投的朋友。有部分兴趣相同的人们就形成了“社交集群”。现请你编写程序，找出所有的集群。

Input:

输入的第一行给出正整数N（<=1000），即社交网络中的用户总数（则用户从1到N编号）。随后N行，每行按下列格式列出每个人的兴趣爱好：

Ki: hi[1] hi[2] … hi[Ki]

其中Ki（>0）是第i个人的兴趣的数量，hi[j]是第i个人的第j项兴趣的编号，编号范围为[1, 1000]内的整数。

Output:

首先在第一行输出整个网络中集群的数量，然后在第二行按非递增的顺序输出每个集群中用户的数量。数字间以1个空格分隔，行首尾不得有多余空格。

Sample Input:

8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4

Sample Output:

3
4 3 1

题目链接

题目使用并查集将兴趣相同的人们划分到一个圈子内，查圈子个数和每个圈内人数。

AC代码:

//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1010;
const double eps = 1e-5;
const double e = 2.718281828459;

int n, k, num;
int cnt = 0;
int course[maxn];
int pre[maxn];
int isroot[maxn];

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

void Init() {
	mem(course, 0);
	mem(isroot, 0);
	for (int i = 0; i <= n; ++i) {
		pre[i] = i;
	}
}

int Find(int x) {
	int r = x;
	while (pre[r] != r) {
		r = pre[r];
	}
	return r;
}

void Join(int x, int y) {
	int xx = Find(x);
	int yy = Find(y);
	if (xx != yy) {
		pre[xx] = yy;
	}
}

void Get_information() {
	cin >> n;
	Init();
	for (int i = 1;i <= n; ++i) {
		scanf("%d:", &k);
		for (int j = 0; j < k; ++j) {
			cin >> num;
			if (course[num] == 0) {
				course[num] = i;
			}
			Join(i, Find(course[num]));
		}
	}
}

void Work() {
	for (int i = 1; i <= n; ++i) {
		isroot[Find(i)]++;
	}
	for (int i = 1; i <= n; ++i) {
		if (isroot[i] != 0) {
			cnt++;
		}
	}
	cout << cnt << endl;
	sort(isroot, isroot + maxn, cmp);
	for (int i = 0; i < cnt; ++i) {
		cout << isroot[i];
		if (i != cnt - 1) {
			cout << " ";
		}
	}
}

int main() {
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    Get_information();
    Work();
    return 0;
}