1107 Social Clusters (30分)

When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A social cluster is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.

Input Specification:

Each input file contains one test case. For each test case, the first line contains a positive integer N (≤), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format:

Ki: hi[1] hi[2] ... hi[Ki]

where Ki (>) is the number of hobbies, and [ is the index of the j-th hobby, which is an integer in [1, 1000].

Output Specification:

For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in non-increasing order. The numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

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
			

				
			


#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a, int b)
{
	return a > b;
}
const int N = 1005;
int father[N], isroot[N] = { 0 }, course[N] = { 0 };
int findfather(int x)
{
	if (father[x] == x)return x;
	else
	{
		int r = findfather(father[x]);
		father[x] = r;
		return r;
	}
}
void unio(int a, int b)
{
	int fa = findfather(a);
	int fb = findfather(b);
	if (fa != fb)
		father[fa] = fb;
}
void init(int x)
{
	for (int i = 1; i <= x; i++)
	{
		father[i] = i;
		isroot[i] = false;
	}
}
int main()
{
	int n,k,h;
	cin >> n;
	init(n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d:", &k);
		for (int j = 1; j <= k; j++)
		{
			cin >> h;
			if (course[h] == 0)//当h活动初始为没人喜欢，则添加i喜欢
			{
				course[h] = i;
			}
			unio(i, findfather(course[h]));//合并同样喜欢h活动人的集合
		}//此题和普通并查集就这里拐了个弯，用course数组保存第一次喜欢i活动人的编号：course[i]=i(hash思想),然后之后有新的人j输入了h，则将j添加到course[i]即i的集合中去，
		//道理还是合并a,b（同样喜欢某活动的），只是用course的套子套在了b的外面也进行了筛选哪些是要合并的数字
	}
	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++;
	}
	cout << ans << endl;
	sort(isroot+1, isroot + n+1,cmp);
	for (int i = 1; i <=ans; i++)
	{
		cout << isroot[i];
		if (i != ans )
			cout << " ";
		else
			cout << endl;
	}
	return 0;
}