Cube Stacking并查集

题目：

https://ac.nowcoder.com/acm/problem/106585

思路：

与传统并查集的区别在于这种每个集合内部的上下关系用rank来维护，各个集合之间的合并因为是整个的所以可以用size来维护

size[i]为根为i的集合的大小

#include<stdio.h>
const int maxn=3e4+7;
int f[maxn],ran[maxn],size[maxn];
void init()
{
for(int i=1;i<=maxn;i++)
{
f[i]=i;
ran[i]=0;
size[i]=1;
}
}
int find(int x)
{
if(x==f[x])
return x;
int t=f[x];
f[x]=find(f[x]);
ran[x]+=ran[t];
return f[x];
}
void merge(int a,int b)
{
int fa=find(a);
int fb=find(b);
f[fa]=fb;
ran[fa]+=size[fb];
size[fb]+=size[fa];//合并了且fb为根
}
int main()
{ init();
int t;
scanf("%d",&t);
char w;
int x,y;
for(int i=1;i<=t;i++)
{
getchar();
scanf("%c",&w);
if(w==‘M‘)
{scanf("%d %d",&x,&y);
merge(x,y);
}
else
{
scanf("%d",&x);
find(x);
printf("%d\n",ran[x]);
}

}
}

Cube Stacking并查集

原文：https://www.cnblogs.com/aacm/p/14860838.html