一、初始化函数：
void init()
{
for(int i=1;i<=n;i++){
pre[i]=i;//每个人的上一个人的编号初始化为自身的编号
}
}
二、找根函数：
1、初始版本：
int findRoot(int x)
{
if(pre[x]==x){//找到最顶层的根节点，则返回其编号，作为当前结点的根结点编号
return x;
}
return findRoot(pre[x]);//否则一直往上找，找其最顶层的根结点
}
2、路径压缩优化版本：
//递归方式：
int findRoot(int x)
{
if(pre[x]==x){//找到最顶层的根节点，则返回其编号，作为当前结点的根结点编号
return x;
}
return pre[x]=findRoot(pre[x]);//否则一直往上找，找其最顶层的根结点,并将路径上的关联点都加到根结点上
}
//迭代方式：
int findRoot(int x)
{
int y=x,t;
while(pre[y]!=y) y=pre[y];
while(x!=y){
t=pre[x];
pre[x]=y;
x=t;//一直往上找，找其最顶层的根结点,并将路径上的关联点都加到根结点上
}
return x;
}
3、递归回溯时记录深度
int getRoot(int x)
{
if(x==pre[x]) return x;
int root=getRoot(pre[x]);//注意这一句要写在更新depth之前！因为要先记录depth[pre[x]]再更新depth[x]
depth[x]+=depth[pre[x]];
return pre[x]=root;
}
三、合并函数：
1、初始版本：
void merge(int x,int y)
{
int px=findRoot(x);//找x的根结点
int py=findRoot(y);//找y的根结点
if(px!=py){//如果x和y根结点不同，即不在一个集合，就把他们合并到一个集合中（即：让一个点的根结点的根结点等于另一个的根结点（就是把一个根结点连到另一个根结点上））
pre[px]=py;
}
}
2、按秩合并优化版本：
int rk[maxn];
void merge(int x,int y)
{
int px=getRoot(x);
int py=getRoot(y);
if(rk[px]>rk[py]){
mp[py]=px;//把层次低的树的根结点连到层次高的数的根结点的下面
}
else{
mp[px]=py;//把层次低的树的根结点连到层次高的数的根结点的下面
if(rk[px]==rk[py]){
++rk[py];//默认一个为相对高的根结点
}
}
}
3、递归回溯时记录深度
void merge(int x,int y)
{
int rx=getRoot(x);
int ry=getRoot(y);
if(rx!=ry){
pre[rx]=ry;
depth[rx]=siz[ry];
siz[ry]+=siz[rx];
}
}
综上，最优版如下：
//初始化函数：
void init()
{
for(int i=1;i<=n;i++){
pre[i]=i;//每个人的上一个人的编号初始化为自身的编号
}
}
//找根函数(+路径压缩)：
int findRoot(int x)
{
if(pre[x]==x){//找到最顶层的根节点，则返回其编号，作为当前结点的根结点编号
return x;
}
return pre[x]=findRoot(pre[x]);//否则一直往上找，找其最顶层的根结点,并将路径上的关联点都加到其下
}
//合并函数（+按秩序合并）：
void merge(int x,int y)
{
int px=getRoot(x);
int py=getRoot(y);
if(rk[px]>rk[py]){
mp[py]=px;//把层次低的树的根结点连到层次高的数的根结点的下面
}
else{
mp[px]=py;//把层次低的树的根结点连到层次高的数的根结点的下面
if(rk[px]==rk[py]){
++rk[py];//默认一个为相对高的根结点
}
}
}
一、初始化函数：
void init()
{
for(int i=1;i<=n;i++){
阅读背景：
并查集模板+（路径压缩&&秩的合并）优化
来源：互联网
分享到：
