0.5 初始化
void set()
{
for(i=
1;i<=n;i++)
fa[i]=i,size[i]=
1;
}
1.路径压缩
int find(
int x)
{
if(fa[x]==x) retrurn x;
else return fa[x]=find(x);
}
2.启发式合并
void union(
int x,
int y)
{
x=find(x),y=find(y);
if(x==y)
return;
if(
size[x]<
size[y]) fa[x]=y,
size[y]+=
size[x];
else fa[y]=x,
size[x]+=
size[y];
}
3.时空复杂度 空间O(n) 时间接近O(1)
