fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
并查集（Union-Find）算法详解 :: labuladong的算法小抄
in my comprehension, as long as we always union the root to another root, regardless the leaf, actually, it could reach more than 3 layer; like: 0 <- 1 <- 2, 3 <- 4 <- 5, union(0,3)
Really appreciate this brilliant explanation of Union Find! But I think the implementation of UF in UC Berkely cs61b course is better.
like: 0 <- 1 <- 2, 3 <- 4 <- 5, union(0,3) This will not happen, coz 0<-1<-2 would be compressed to 2>-0<-1, with height 1, when you union them. so does 3,4,5.
@MrHedwig It's still gonna happen. 0 <- 1 and 2 <- 3 going to make a 3 level relationship of 1 -> 0 <- 2 <- 3. Then @yzw-Joey 's case is going to happen when union 2 of 3 level relationship
将Union find这个算法描述成等价关系太精彩了。
Union find利用根节点，巧妙的实现了自反性，对称性和传递性。
生活中除了等价关系还有一类比较常见的关系，偏序关系(自反性，反对称性，传递性)。请问有人了解偏序关系应该用什么算法处理？或者是否能在UF上做修改，使其适用于偏序关系呢？
@xixiang87 1-> 0 <- 2 <- 3, for this case, I don't thin it is 3 level. It belongs to 2 levels.
@xixiang87 I guess you are right. In case we have 0, 1, 2, 3, 4, 5, 6, 7 with Union(0, 1), Union(2, 3), Union(4, 5), Union(6, 7) (and take smaller number as root) Then Uion(0, 2), Union(4, 6) Finally Union(2, 4).
Here the issue is each time we Union with root, so path compression in find method is not ever triggered... @labuladong idea how to avoid scenarios like this?
js 版
class UF {
constructor(n) {
// 一开始互不连通
this._count = n;
// 父节点指针初始指向自己
this._parent = new Array(n).fill(0).map((_, index) => index);
// 最初每棵树只有一个节点
// 重量应该初始化 1
this._weights = new Array(n).fill(1);
}
union(p, q) {
const rootP = this.findRoot(p);
const rootQ = this.findRoot(q);
if (rootP === rootQ) return;
// 将两棵树合并为一棵
// 小树接到大树下面，较平衡
const weights = this._weights;
if (weights[rootP] > weights[rootQ]) {
this._parent[rootQ] = rootP;
weights[rootQ]++;
} else {
this._parent[rootP] = rootQ;
weights[rootP]++;
}
this._count--; // 两个分量合二为一
}
// 返回某个节点 x 的根节点
findRoot(x) {
const parent = this._parent;
while (parent[x] !== x) {
// 进行路径压缩
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
connected(p, q) {
const rootP = this.findRoot(p);
const rootQ = this.findRoot(q);
return rootP === rootQ;
}
count() {
return this._count;
}
}
@xixiang87 I guess you are right. In case we have 0, 1, 2, 3, 4, 5, 6, 7 with Union(0, 1), Union(2, 3), Union(4, 5), Union(6, 7) (and take smaller number as root) Then Uion(0, 2), Union(4, 6) Finally Union(2, 4).
Here the issue is each time we Union with root, so path compression in find method is not ever triggered... @labuladong idea how to avoid scenarios like this?
As I revisited this question I raised... I realized that although tree size grows, it doesn't matter. Coz we care about Union and Find are amortized O(1), if we Union root, then find(root) is itself O(1), i.e. returns immediately.
Thus if we always Union by root, it doesn't violate the amortized O(1) rule, which is really what matters eventually. @xixiang87 @yzw-Joey @labuladong
本文内容已更新，合并了 union-find 算法的应用，并且在使用路径压缩的技巧时去除了 size 数组。因为就像有的读者说的，路径压缩之后 size 数组的作用已经不大，而且在路径压缩的过程中正确维护 size 数组有些麻烦，所以现在比较推荐的写法是只使用路径压缩技巧，即文中的 UF 类代码。
private int find(int x) {
while (parent[x] != x) {
// 进行路径压缩
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
东哥这种路径压缩可以在多数条件下保证树的高度不会太高（也就是查找任意节点的根节点的时间复杂度为 O(1)）。
但是想上面 @MrHedwig 哥举的这种特殊情况，就会导致树的高度逐渐增长。
在 LeetCode 上刷题看见官方的解法，在 find 的查找节点根节点的过程中，查找路径上的各个节点都会进行“压缩”操作，使路径上的所有节的直接父节点变为根结点，那么可以保证查找任意节点的根节点的时间复杂度为 O(1)，代码如下：
public int find(int i) {
if (parent[i] != i) {
parent[i] = find(parent[i]);
}
return parent[i];
}
@labuladong 确实，没办法解决那种特殊情况的问题。不过这个压缩效果会好一点。
这种递归的写法做的事情和迭代写法是一模一样的啊，就是把形式改成递归的了，还让人不容易理解。这种写法的效果好在哪里呢，是否能举出例子？
@labuladong 这个递归和迭代不太一样，东哥你写的迭代，是在从当前结点到根结点遍历的过程中，所有遍历的到的结点的父节点都指向其祖先（爷爷）结点；那个递归是路径上的所有结点的父节点都设置为根结点。
这个find的写法
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
// 要加上 x = parent[x]; x 不变会死循环吧。
}
return parent[x];
}
