Union-Find总结

Union-Find是什么

详情参考：

1. labuladong的算法小抄——Union-Find算法详解
2. labuladong的算法小抄——Union-Find算法应用
3. 花花酱的Union-Find视频

Union-Find其实是一种解决图的连通性问题的算法。或者说解决某张图里连通分量的问题。比如说最简单的Number of Islands，就是查找图里有多少个连通分量。

其实并查集的问题并不多，而且绝大多数并查集用DFS也都能够解决，union-find主要是一种思想，某些情况下会有不错的效果。

Union-Find基础思路

思想推导

基本操作Union与Find

这里推导只是简单的文字描述，作图的话时间不太充沛，以后有机会再补，觉得看不懂可以参考第一节里的参考资料，里面有很详细的分析。

首先，我们假设有n个独立的节点，我们定义每个节点i存在它的parent[i]，初始化为自己本身。

然后我们定义两种操作，Union和Find。

1. Union的过程就是将两个节点连接起来的过程，如果我们Union(a, b)，那么我们就将a的parent节点设置为b。
2. Find的过程就是找到某节点的root节点，root节点就是一级一级向上找，直到找到某个节点的parent节点是本身，该节点就是root节点。

优化

Path Regression（Find优化）

在find的时候，每次找到root节点时，可以将路径上所有节点的parent全部都指向root节点，这样的话可以保证树的高度不会很高，每次查询都可降低后续查询的复杂度。

Merge Optimization（Union优化）

在Union的时候，我们希望把比较小的树连接到比较大的树上，这样整棵树的高度不会更高。因此我们需要一个size，来记录每棵树的大小。

基础代码

class UF {
    int[] parent; // 每个连通分量的父节点
    int[] size; // 每个连通分量的大小
    int count; // 当前有多少个连通分量

    public UF (int n) {
        parent = new int[n];
        size = new int[n];
        count = n;

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    // 合并的时候把size小的merge到高的上
    public void union(int a, int b) {
        int rootA = findRoot(a);
        int rootB = findRoot(b);
        if (rootA == rootB) {
            return;
        }

        if (size[rootA] >= size[rootB]) {
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
        } else {
            parent[rootA] = rootB;
            size[rootB] += size[rootA];
        }
        count--;
    }

    // 找到根节点这种写法是将树的高度压缩为3以内
    // private int findRoot(int x) {
    //     while (x != parent[x]) {
    //         parent[x] = parent[parent[x]];
    //         x = parent[x];
    //     }
    //     return x;
    // }
    //这种写法是把树的高度压缩成2，一个根带多个孩子
    public int findRoot(int x) {
        if (x != parent[x]) {
            parent[x] = findRoot(parent[x]);
        }
        return parent[x];
    }
}

拓展：有向图的Union-Find

经典题目就是：LeetCode 685. Redundant Connection II

Union-Find应用题目

1. LeetCode 547. Friend Circles
2. LeetCode 399. Evaluate Division
3. LeetCode 684. Redundant Connection
4. LeetCode 685. Redundant Connection II
5. LeetCode 130. Surrounded Regions