描述
递归版本find函数有些同学不好理解,这里放出一个迭代版本find函数。
C++ 代码
int find(int x) {
// 查找x元素所属的集合,用r (root)表示根节点
int r = x;
while (p[r] != r) r = p[r];
// 路径压缩,把所有子节点指向根节点r
while (p[x] != x) {
int t = p[x];
p[x] = r;
x = t;
}
return r;
}
第二个while(p[x]!=x)里面写错了吧,是不是应该先把这temp=p[x]记录下来了,然后p[x]=t,x=temp;
感谢指正,已修改。