并查集的非递归路径压缩

佚名 4年前 (2020-01-17) 随笔 2045人围观抢沙发百度已收录

我们知道，递归版路径压缩的实质就是在回溯过程中把沿途出现的爸爸变成兄弟，最终由N代同堂变成二代同堂。

所以我们可以利用这样的方法写出非递归路径压缩。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

首先要找到根节点root，然后从当前位置出发寻找根节点，沿途得到的父亲节点father全部直接指向根节点。

如何得到沿途的父节点呢？当然是迭代啦！

 1 int find(int d)
 2 {
 3     int now,temp,root;
 4     
 5     root=d;
 6     while(root!=father[root])
 7     {
 8         root=father[root];
 9     }
10     now=d;
11     while(now!=root)
12     {
13         temp=father[now];
14         father[now]=root;
15         now=temp;
16     }
17     return root;
18 }