并查集（Union-Find）算法详解 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：并查集（Union-Find）算法详解

评论礼仪 见这里，违者直接拉黑。

[yzw-Joey]

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)

[Park-J-lab]

Really appreciate this brilliant explanation of Union Find! But I think the implementation of UF in UC Berkely cs61b course is better.

[Feyl]

@yzw-Joey The layers will be decrease when you find other nodes in the union.

[MrHedwig]

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.

[xixiang87]

@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

[0xlightyear]

将Union find这个算法描述成等价关系太精彩了。

Union find利用根节点，巧妙的实现了自反性，对称性和传递性。

生活中除了等价关系还有一类比较常见的关系，偏序关系(自反性，反对称性，传递性)。请问有人了解偏序关系应该用什么算法处理？或者是否能在UF上做修改，使其适用于偏序关系呢？

[EhanDuan]

@xixiang87 1-> 0 <- 2 <- 3, for this case, I don't thin it is 3 level. It belongs to 2 levels.

[MrHedwig]

@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?

[LovesAsuna]

最后的那个find的优化的gif图是不是错了？将parent[x]=parent[parent[x]]之后，x不应该是原来的父节点啊

[jswxwxf]

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;
  }
}

[qq1545372477]

进行路径压缩的时候不需要调整size数组么？

[MrHedwig]

@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

[labuladong]

本文内容已更新，合并了 union-find 算法的应用，并且在使用路径压缩的技巧时去除了 size 数组。因为就像有的读者说的，路径压缩之后 size 数组的作用已经不大，而且在路径压缩的过程中正确维护 size 数组有些麻烦，所以现在比较推荐的写法是只使用路径压缩技巧，即文中的 UF 类代码。

[Feyl]

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];
    }

代码出处：1020.飞地的数量 官方题解的并查集解法

[labuladong]

@Feyl 你说的官方题解这种递归实现的 find 方法，也无法避免每次 union 两个根节点导致的树高增加的情况呀

[chaonanzhang1206]

看到很多人的模板是加入一个 int[] rank 而不是 int[] size, 有必要吗？

[Feyl]

@labuladong 这个递归和迭代不太一样，东哥你写的迭代，是在从当前结点到根结点遍历的过程中，所有遍历的到的结点的父节点都指向其祖先（爷爷）结点；那个递归是路径上的所有结点的父节点都设置为根结点。

[labuladong]

@Feyl 你说的对哦👍，我大意了，这个递归解法确实精妙，我补充到文章里。

[CNforwardmarch]

东哥，为啥我感觉这两种压缩算法find都会出现数不断增高的情况。复杂度是怎么为O(1)的呢

[labuladong]

@CNforwardmarch 不会啊，你举个例子画个图就明白了，find 调用在不断减少树高，不会增高的。

[deepbreath373]

check in

[chouxi]

这个find的写法

public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
        // 要加上 x = parent[x]; x 不变会死循环吧。
    }
    return parent[x];
}

[DeathKnightH]

不会，这里是递归，不是迭代。
每次传给下一层递归的都是新的 parent[x]，而最后一层递归的终止条件就是 x == parent[x] ，不会造成死循环的。

[piaomiaoaxin]

c++

并查集Union-Find

class UF{
private:
    int count;//连通分量
    vector<int> parent;//存储每个节点的父节点

public:
    UF(int n){
        this->count = n;//连通分量初始化
        parent.resize(n);
        //初始化节点的父节点为节点自身
        for (int i = 0; i < n; ++i) {
            parent[i]=i;
        }
    }

    //将节点p和q连通
    void doUnion(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);

        //p和q已经连通
        if (rootP == rootQ){
            return;
        }
        parent[rootQ] = rootP;
        count--;//两个连通分量合并为一个
    }

    bool connected(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    int find(int x){
        if (parent[x] != x){
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    //const成员
    const int& getCount() const{
        return count;
    }
};

[Lihp0521]

请问，力扣第 130 题「 被围绕的区域」中，判断内层数组的元素与相邻边界的元素都为'O'的时候，为什么内层的元素要与相邻边界元素相连而不能直接和dummy连接呢？

// 方向数组 d 是上下左右搜索的常用手法
    int[][] d = new int[][]{{1,0}, {0,1}, {0,-1}, {-1,0}};
    for (int i = 1; i < m - 1; i++) 
        for (int j = 1; j < n - 1; j++) 
            if (board[i][j] == 'O')
                // 将此 O 与上下左右的 O 连通
                for (int k = 0; k < 4; k++) {
                    int x = i + d[k][0];
                    int y = j + d[k][1];
                    if (board[x][y] == 'O')
                        uf.union(x * n + y, i * n + j);
                          // uf.union(dummy, i * n + j); 使用这一行代码会报错，为什么不能是与dummy连接呢？
                }

还请各位大佬解答。

[zwtu]

因为x * n + y 并不一定是边界元素

[AiGaoShiBOY]

我觉得递归的find可以这样理解，因为并查集底部可以看作由数组实现的一个链表, 即parent[x] = x.next(我觉得这样好懂一些)，那么这段代码可以翻译成:

def find(x):
    if x != root:
         x.next = find(x.next)
    return x.next

看到函数的返回条件，就可以理解为函数会一直往前走，直到走到根节点的时候才会return。由于根节点的next指向的是自己，所以函数会返回的就是根节点。然后这个根节点把值依次赋给一路走来的节点，这样就把所有节点都拉平了。

[juffyduan]

union(p, q) {
    let rootQ = this.find(q);
    let rootP = this.find(p);
            
    // 如果两个节点已经在同一个连通分量内，不用合并
    if (rootP === rootQ) {
        return;
    }

    // 根据树高，优化合并性能，避免树变的很高
    if (this.size[rootP] > this.size[rootQ]) {
        this.parent[rootQ] = rootP;
    } else if(this.size[rootP] < this.size[rootQ]){
        this.parent[rootP] = rootQ;
    } else {
        this.parent[rootQ] = rootP;
        this.size[rootP] += this.size[rootQ];
        // this.parent[rootP] = rootQ;
        // this.size[rootQ] += this.size[rootP];
    }
    
    this.count--;
}

["a==b","e==c","b==c","a!=e"]
使用注释的代码，这个case会失败，百思不解，东哥求解

[kids-p]

引用：“使用UF解决岛屿系列问题的部分”
想问一下，如果按照博主的写法，是否会导致，漏掉与边界相连的‘0’节点，因为类似这里一次性从上到下遍历完整个矩阵，但是如果相连的节点是往上继续联通的，那么将没有能力遍历到上面的节点？是这样吗

void solve(char[][] board) {
    if (board.length == 0) return;

    int m = board.length;
    int n = board[0].length;
    // 给 dummy 留一个额外位置
    UF uf = new UF(m * n + 1);
    int dummy = m * n;
    // 将首列和末列的 O 与 dummy 连通
    for (int i = 0; i < m; i++) {
        if (board[i][0] == 'O')
            uf.union(i * n, dummy);
        if (board[i][n - 1] == 'O')
            uf.union(i * n + n - 1, dummy);
    }
    // 将首行和末行的 O 与 dummy 连通
    for (int j = 0; j < n; j++) {
        if (board[0][j] == 'O')
            uf.union(j, dummy);
        if (board[m - 1][j] == 'O')
            uf.union(n * (m - 1) + j, dummy);
    }
    // 方向数组 d 是上下左右搜索的常用手法
    int[][] d = new int[][]{{1,0}, {0,1}, {0,-1}, {-1,0}};
    for (int i = 1; i < m - 1; i++) 
        for (int j = 1; j < n - 1; j++) 
            if (board[i][j] == 'O')
                // 将此 O 与上下左右的 O 连通
                for (int k = 0; k < 4; k++) {
                    int x = i + d[k][0];
                    int y = j + d[k][1];
                    if (board[x][y] == 'O')
                        uf.union(x * n + y, i * n + j);
                }
    // 所有不和 dummy 连通的 O，都要被替换
    for (int i = 1; i < m - 1; i++) 
        for (int j = 1; j < n - 1; j++) 
            if (!uf.connected(dummy, i * n + j))
                board[i][j] = 'X';
}

class UF {
    // 见上文
}

比如对于博主所列出的矩阵中的[1, 1]节点如果也为'O'，那么将漏掉这个点

[lemonzeng]

Leetcode 323:
public int find(int n){ if(parent[n] != n){//写成 while() 会造成死循环——但不知道为啥 parent[n] = find(parent[n]); }
如果if改为while会变成死循环，可否解答一下？
test case: 5
[[0,1],[1,2],[0,2],[3,4]]

class Solution {
    class UF{
        private int count;
        private int[] parent;
        public UF(int n){
            this.count = n;
            parent = new int[n];
            for(int i=0; i < n; i++){
                parent[i] = i;
            }
        }
        public int find(int n){
            if(parent[n] != n){//写成 while() 会造成死循环——但不知道为啥
                parent[n] = find(parent[n]);
            }
            return parent[n];
        }
        public void union(int p, int q){
            int rootP = find(p);
            int rootQ = find(q);
            if(rootP == rootQ){
                return;
            }
            parent[rootP] = rootQ;
            count--;
        }
        public int count(){
            return count;
        }
    }
    public int countComponents(int n, int[][] edges) {
        UF uf = new UF(n);
        for(int[] edge: edges){
            uf.union(edge[0], edge[1]);
        }
        return uf.count();
    }
}

[10-Kirito]

那个递归的路径压缩的方法，可以不可以理解为，一开始我们合并的时候在极端的情况下，得到的树是一直在增高的。伴随着后面在查找的过程当中对其进行调整，进行压缩，查找的多了，之后再次进行查找的时候，时间复杂度就是O(1)。

[codezs09]

find 递归路径压缩可以写成以前讲过的后序的形式，更容易理解。

class UF {
   // 递归路径压缩
    public int find(int x) {
        if (parent[x] == x) {
             return x;      // 终止条件： 返回root根节点
        }

        int root = find(parent[x]);   // 是不是很熟悉类似递归 traverse
        
        // 后序位置 赋值 x 的 parent
        parent[x] = root; 
        
        return root;     // 也可以 return  parent[x]， 因为此时 parent[x] = root
    }
}

仔细对照，是不是完全等效于原文的方法（如下），而且更好理解

class UF {
   // 递归路径压缩
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
}