2.6.「并查集」数据结构总结

在「并查集」数据结构中，其中心思想是将所有连接的顶点，无论是直接连接还是间接连接，都将他们指向同一个父节点或者根节点。此时，如果要判断两个顶点是否具有连通性，只要判断它们的根节点是否为同一个节点即可。

在「并查集」数据结构中，它的两个灵魂函数，分别是 find和 union。find 函数是为了找出给定顶点的根节点。 union 函数是通过更改顶点根节点的方式，将两个原本不相连接的顶点表示为两个连接的顶点。对于「并查集」来说，它还有一个重要的功能性函数 connected。它最主要的作用就是检查两个顶点的「连通性」。find 和 union 函数是「并查集」中必不可少的函数。connected 函数则需要根据题目的意思来决定是否需要。

「并查集」代码基本结构

public class UnionFind {
    // UnionFind 的构造函数，size 为 root 数组的长度
    public UnionFind(int size) {}
    public int find(int x) {}
    public void union(int x, int y) {}
    public boolean connected(int x, int y) {}
}

「并查集」的 find 函数

它主要是用于查找顶点 x 的根结点。

• find 函数的基本实现

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

• find 函数的优化 - 路径压缩

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

「并查集」的 union 函数

它主要是连接两个顶点 x 和 y 。将它们的根结点变成相同的，即代表它们来自于同一个根节点。

• union 函数的基本实现

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

• union 函数的优化 - 按秩合并

public void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY]) {
            root[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            root[rootX] = rootY;
        } else {
            root[rootY] = rootX;
            rank[rootX] += 1;
        }
    }
};

「并查集」的 connected 函数

它主要是检查两个顶点 x 和 y 的「连通性」。这个函数通过顶点 x 和 y 的根结点是否相同来判断 x 和 y 的「连通性」。如果 x 和 y 的根结点相同，则为连通。反之，则为不连通。

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

「并查集」的刷题小技巧

「并查集」的代码是高度模版化的。所以作者建议大家熟记「并查集」的实现代码，这样小伙伴们在遇到「并查集」的算法题目的时候，就可以淡定的应对了。作者推荐大家在理解的前题下，请熟记「基于路径压缩+按秩合并的并查集」的实现代码。