并查集练习 1107 Social Clusters (30分)
程序员文章站
2022-06-11 12:06:54
...
关于有关并查集的题主要应掌握两点:
father[]数组:记录每个结点的父结点
findAncestor():找到该结点所在集合的根结点
1107 Social Clusters (30分)
该题中还需要求出每个集合中结点的个数,因此只需设置一个isAncestor[]数组,isAncestor[i]表示以i作为根结点的集合中有多少结点,若i不是根结点,则isAncestor[i]=0。
for (int i = 1; i <= n; i++)
isAncestor[findAncestor(i)]++;
const int maxn = 1010;
int lastPerson[maxn] = { 0 }; //记录当前喜欢某活动的最后一个人
int father[maxn];
int isAncestor[maxn] = { 0 };
int findAncestor(int x)
{
if (father[x] == x)
return x;
else
return findAncestor(father[x]);
}
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
int n, act,num;
scanf("%d", &n);
//人从1开始编号,初始化father数组
for (int i = 1; i <= n; i++)
father[i] = i;
for (int i = 1; i <= n; i++)
{
scanf("%d: ", &num);
for (int j = 0; j < num; j++)
{
scanf("%d", &act);
//已经有人喜欢该活动
if (lastPerson[act] != 0)
{
int lp = lastPerson[act];
int anc1 = findAncestor(i);
int anc2 = findAncestor(lp);
//若这两个结点还没有在同一个集合中,合并
if (anc1 != anc2)
father[anc1] = anc2;
}
lastPerson[act] = i;
}
}
int uNum = 0;
for (int i = 1; i <= n; i++)
isAncestor[findAncestor(i)]++;
for (int i = 0; i < maxn; i++)
if (isAncestor[i] != 0)
uNum++;
printf("%d\n", uNum);
sort(isAncestor, isAncestor + maxn, cmp);
for (int i = 0; i < uNum-1; i++)
printf("%d ", isAncestor[i]);
printf("%d", isAncestor[uNum-1]);
}