2.4.路径压缩优化的「并查集」

从前面的「并查集」实现方式中，我们不难看出，要想找到一个元素的根节点，需要沿着它的父亲节点的足迹一直遍历下去，直到找到它的根节点为止。如果下次再查找同一个元素的根节点，我们还是要做相同的操作。那我们有没有什么办法将它升级优化下呢？

答案是可以的！如果我们在找到根节点之后，将所有遍历过的元素的父节点都改成根节点，那么我们下次再查询到相同元素的时候，我们就仅仅只需要遍历两个元素就可以找到它的根节点了，这是非常高效的实现方式。那么问题来了，我们如何将所有遍历过的元素的父节点都改成根节点呢？这里就要拿出「递归」算法了。这种优化我们称之为「路径压缩」优化，它是对 find 函数的一种优化。

伪代码

// UnionFind.class
public class UnionFind {
    int root[];

    public UnionFind(int size) {
        root = new int[size];
        for (int i = 0; i < size; i++) {
            root[i] = i;
        }
    }

    public int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]);
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            root[rootY] = rootX;
        }
    };

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

// App.java
// 测试样例
public class App {
    public static void main(String[] args) throws Exception {
        UnionFind uf = new UnionFind(10);
        // 1-2-5-6-7 3-8-9 4
        uf.union(1, 2);
        uf.union(2, 5);
        uf.union(5, 6);
        uf.union(6, 7);
        uf.union(3, 8);
        uf.union(8, 9);
        System.out.println(uf.connected(1, 5)); // true
        System.out.println(uf.connected(5, 7)); // true
        System.out.println(uf.connected(4, 9)); // false
        // 1-2-5-6-7 3-8-9-4
        uf.union(9, 4);
        System.out.println(uf.connected(4, 9)); // true
    }
}

时间复杂度

注：N 为「图」中顶点的个数。