思路
对兴趣点进行查并集的合并操作。即在输入过程中不断的合并有共同兴趣点的兴趣点集合,并且将合并后的集合人数统计出来,之后就是排序什么的了。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
// 记录兴趣点集合的祖先编号
int interest[MAXN];
// 记录每个集合树的高度,优化查并集操作的速度
int high[MAXN];
// 对应记录数组下标代表的兴趣点编号拥有的人数
int people[MAXN];
// 获取兴趣点编号为 x 的所在兴趣集合的祖先编号
int getRoot(int x)
{
return x == interest[x] ? x : interest[x]=getRoot(interest[x]);
}
// 合并两个编号为 x 和编号为 y 的兴趣点所在集合
void merge(int x, int y)
{
int rootX = getRoot(x);
int rootY = getRoot(y);
if (rootX != rootY)
{
if (high[rootX] < high[rootY])
{
interest[rootX] = rootY;
}
else
{
interest[rootY] = rootX;
if (high[rootX] == high[rootY])
{
high[rootX]++;
}
}
}
}
void init()
{
for (int i = 1; i < MAXN; i++)
{
// 初始状态,每个兴趣点集合祖先都是它本身
interest[i] = i;
}
}
int main()
{
init();
int n, m, inte, inte1;
cin >> n;
for (int i = 0; i < n; i++)
{
scanf("%d: %d", &m, &inte);
// 输入的过程中合并不同的兴趣点组成兴趣点集合
for (int j = 1; j < m; j++)
{
scanf("%d", &inte1);
merge(inte, inte1);
}
// 对应兴趣点集合的祖先所拥有的人数加一
people[getRoot(inte)]++;
}
int setSum = 0, tempRoot;
for (int i = 1; i < MAXN; i++)
{
tempRoot = getRoot(i);
if (people[i])
{
// 如果兴趣点编号等当前兴趣点集合祖先的编号,
// 那么集群数量加一
if (i == tempRoot)
{
setSum++;
}
else
{
// 否则就是某个兴趣点集合的子集,即为某个集群的子集,
// 那么对应的集群祖先拥有的人数就要加上当前兴趣点子集拥有的人数
people[tempRoot] += people[i];
people[i] = 0;
}
}
}
sort(people, people+MAXN, greater<int>());
cout << setSum << endl;
for (int i = 0; i < setSum; i++)
{
if (i)
{
cout << " ";
}
cout << people[i];
}
return 0;
}