算法工具——并查集 – 哈冬猪的小站

引子

并查集（disjoint-set data structure/union–find data structure）以不相交的子集的形式储存集合，它有以下功能：

（并）合并两个子集
（查）查找元素所属子集（衍生：判断两个元素是否属于同一个子集）

实现（C++）

通常，并查集由树形结构实现。树储存在数组中，数组中的值代表父节点，若父节点为自己则代表为根节点。初始状态下，每个元素都属于独立的子集，即每个元素都是根节点。根据不同的策略（快查/快并）并查集的实现也不完全相同。

快查

在快查策略下，我们希望树的深度最大只有2，从而实现查询速度最快，在每次合并时都需要将一个子集的所有元素的根变更为另一子集的根。

#include <vector>
#include <algorithm>
#include <numeric>

struct union_find {
    std::vector<int> nodes;

    explicit union_find(int number) {
        nodes = vector<int>(number);
        /* cpp 11 */
        std::iota(nodes.begin(), nodes.end(), 0);
        /* cpp 98 */
//        for(vector<int>::size_type i = 0; i < nodes.size(); i++)
//        {
//            nodes[i] = i;
//        }
    };

    int find(int node) {
        return nodes[node];
    };

    void unite(int node1, int node2) {

        int root1 = find(node1);
        int root2 = find(node2);

        /* cpp 11 */
        for(int & node : nodes) {
            if(find(node) == root1)
                node = root2;
        }
        /* cpp 98 */
//        for(vector<int>::size_type i = 0; i < nodes.size(); i++)
//        {
//            if(nodes[i] == root1)
//            {
//                nodes[i] = root2;
//            }
//        }
    };

    bool is_in_same_set(int node1, int node2) {
        return find(node1) == find(node2);
    }
};

快并

在快并策略下，不要求树的深度，在合并操作时将一个集合的根节点指向另一个集合的根节点，从而实现快速合并。


#include <vector>
#include <algorithm>
#include <numeric>


struct union_find {
    std::vector<int> nodes;

    explicit union_find(int number) {
        nodes = vector<int>(number);
        /* cpp 11 */
        std::iota(nodes.begin(), nodes.end(), 0);
        /* cpp 98 */
//        for(vector<int>::size_type i = 0; i < nodes.size(); i++)
//        {
//            nodes[i] = i;
//        }
    };

    int find(int node) {

        /* 递归 */
        return node == nodes[node] ? node : find(nodes[node]);
        /* 迭代 */

//        while (node != nodes[node]) {
//            node = nodes[node];
//        }
//        return node;
    };

    void unite(int node1, int node2) {
        nodes[find(node1)] = find(node2);
    };

    bool is_in_same_set(int node1, int node2) {
        return find(node1) == find(node2);
    }
};

但是，这样简单合并可能导致树深度过大（树的退化），导致查询速度大幅下降，因此可以在查询或合并时进行优化，避免树的深度过大。

路径压缩（查询时优化）

隔代压缩

在查询时将节点指向父节点的父节点。

    int find(int node) {
        while (node != nodes[node]) {
            node = nodes[node] = nodes[nodes[node]];
        }
        return node;
    };

完全压缩

在查询时将所有节点都指向根节点。

    int find(int node) {
        return node == nodes[node] ? node : nodes[node] = find(nodes[node]);

    };

按秩合并（合并时优化）

在合并时就避免增加树的深度。由于将一颗树的父节点指向另一个树的根会导致树的深度+1，因此将深度小/节点数目少的树连接到深度大或/节点数目多的树上。因此需要一个新的数组来储存秩，并初始化。

struct union_find {
    std::vector<int> nodes;
    std::vector<int> ranks;

    explicit union_find(int number) {
        nodes = vector<int>(number);
        ranks = vector<int>(number, 1);
        /* cpp 11 */
        std::iota(nodes.begin(), nodes.end(), 0);
        /* cpp 98 */
//        for(vector<int>::size_type i = 0; i < nodes.size(); i++)
//        {
//            nodes[i] = i;
//        }
    };
};

按深度合并

    void unite(int node1, int node2) {

        int root1 = find(node1);
        int root2 = find(node2);
        if (root1 == root2) {
            return;
        }

        if (ranks[root1] > ranks[root2]) {
            nodes[root2] = root1;
        }
        else if (ranks[root1] < ranks[root2]) {
            nodes[root1] = root2;
        }
        else {
            nodes[root2] = root1;
            ranks[root2]++;
        }
    };

按节点数目合并

    void unite(int node1, int node2) {

        int root1 = find(node1);
        int root2 = find(node2);
        if (root1 == root2) {
            return;
        }

        if (ranks[root1] > ranks[root2]) {
            nodes[root2] = root1;
            ranks[root1] += ranks[root2];
        }
        else if (ranks[root1] < ranks[root2]) {
            nodes[root1] = root2;
            ranks[root2] += ranks[root1];
        }
        else {
            nodes[root2] = root1;
            ranks[root1] += ranks[root2];
        }
    };

应用

最小生成树算法（Kruskal算法）（贪心）

引子