并查集定义

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。

名字取自：Union、Find、Set 三个单词，Union-Find Disjoint Sets。

并查集的实现就是用一个数组：father[]

father[i] 表示元素 i 的父亲结点，而父亲结点本身也是这个集合的元素（1 <= i <= N）
若 father[i] == i 则说明元素 i 是该集合的根结点
对同一个集合而言，只有一个根节点，将其作为该集合的标识

此外，并查集的实现也可以用一个 Map 来实现：

java

1	Map<Integer, Integer> father;

并查集产生的每一个集合都是一棵树

基本操作

并查集的使用需要先初始化 father 数组，然后再根据需要进行查找或者合并的操作。

初始化

一开始，每个元素都是独立的一个集合，因此所有的 father[i] = i

java

public void init(int n) {
    father = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
}

查找

由于一个集合只有一个根结点，因此查找操作就是根据给定的结点寻找其根结点的过程，可以使用递推/递归的方式，思路都一样：反复寻找父亲结点，直至找到根节点（father[i] = i）

java

// 递推
public int find(int x) {
    while (x != father[x]) {
        x = father[x];
    }
    return x;
}

// 递归
public int find(int x) {
    if (x == father[x]) {
        return x;
    } else {
        return find(father[x]);
    }
    // return father[x] == x ? x : find(father[x]);
}

合并

根据给定的两个元素，将其所在的集合合并，步骤如下：

判断给定的两个元素 a、b 是否属于同一个集合，用查找找出根结点 faA、faB，判断是否相同，若相同则直接结束；否则进入下一步，将两个集合合并
根据 1 中获得的两个根结点 faA、faB，只需要将其中一个的父亲结点指向另一个结点即可，father[faA] = faB 或者 father[faB] = faA

java

public void union(int a, int b) {
    int faA = find(a);
    int faB = find(b);
    if (faA != faB) {
        father[faA] = faB;
    }
}

计数

我们可以通过遍历 father[] 来获得集合的个数，但是效率较低。最高效的方法是维护一个变量 count，初始化成 father[] 的大小，然后每次 union() 成功后减一，便可高效计数。

路径压缩

并查集没有优化的话，在极端情况下效率很低，为 $O(n)$ ，退化为链式树。

由于 find 函数就是为了找到根结点，因此我们可以将 father 优化，使其直接指向根结点，将查找操作时间复杂度降低到 $O(1)$

路径压缩

路径压缩的步骤如下：

按原先的方法获取 x 的根结点 r
重新从 x 开始走一遍寻找根结点的过程，把路径上经过的所有结点的父亲全部改为根结点 r

java

// 递推
public int find(int x) {
    int a = x;
    while (x != father[x]) {
        x = father[x];
    }
    while (a != father[a]) {
        int temp = a;
        a = father[a];
        father[temp] = x;
    }
    return x;
}

// 递归
public int find(int x) {
    if (x == father[x]) {
        return x;
    } else {
        int f = find(father[x]);
        father[x] = f;
        return f;
    }
}

虽然在 find 的过程中进行了路径压缩，但是 find 的均摊效率近乎为 $O(1)$

并查集的应用

LeetCode 399.除法求值：

image-20210404111642646

这个其实是一个图问题：给定图中的一些点（变量），以及某些边的权值（两个变量的比值），试对任意两点（两个变量）求出其路径长（两个变量的比值）。

java

public class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int equationSize = equations.size();

        UnionFind unionFind = new UnionFind(2 * equationSize);
        // 第 1 步：预处理，将变量的值与 id 进行映射，使得并查集的底层使用数组实现，方便编码
        Map<String, Integer> map = new HashMap<>(2 * equationSize);
        int id = 0;
        for (int i = 0; i < equationSize; i++) {
            List<String> equation = equations.get(i);
            String x = equation.get(0);
            String y = equation.get(1);
            if (!map.containsKey(x)) {
                map.put(x, id++);
            }
            if (!map.containsKey(y)) {
                map.put(y, id++);
            }
            unionFind.union(map.get(x), map.get(y), values[i]);
        }

        int querySize = queries.size();
        double[] ans = new double[querySize];
        for (int i = 0; i < querySize; i++) {
            String x = queries.get(i).get(0);
            String y = queries.get(i).get(1);

            Integer id1 = map.get(x);
            Integer id2 = map.get(y);
            if (id1 == null || id2 == null) {
                ans[i] = -1.0d;
            } else {
                ans[i] = unionFind.isConnected(id1, id2);
            }
        }

        return ans;
    }

    class UnionFind {
        private int[] parent;
        private double[] weight;

        public UnionFind(int n) {
            this.parent = new int[n];
            this.weight = new double[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                weight[i] = 1.0d;
            }
        }

        public void union(int x, int y, double value) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                parent[rootX] = rootY;
                // 这里需要推导一下
                weight[rootX] = weight[y] * value / weight[x];
            }
        }

        public int find(int x) {
            if (x != parent[x]) {
                int origin = parent[x];
                parent[x] = find(parent[x]);
                weight[x] *= weight[origin];
            }
            return parent[x];
        }

        public double isConnected(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return weight[x] / weight[y];
            } else {
                return -1.0d;
            }
        }
    }
}