联合查找（或不相交集合）数据结构在STL中吗？

Question

我本以为这样一个有用的数据结构会被包含在C++标准库中，但我似乎找不到。

- Ritwik Biswas

---

https://dev59.com/tG855IYBdhLWcg3wKw9Y - user2100815

我认为它的实用性不够广泛，因此值得去标准化、实现和维护的麻烦。 （我的直觉是受益于它的C ++项目的百分比接近于零而非一。） - molbdnilo

Answer 1

不是很常见，但boost库中有一个: http://www.boost.org/doc/libs/1_64_0/libs/disjoint_sets/disjoint_sets.html，如果你需要一个现成的实现，我建议使用它。

- Nir Friedman

---

没有文档说明，典型的Boost风格非常泛泛，但是这个回答和这个回答提供了如何使用它的想法。 - Timmmm

Answer 2

不需要，我已经写了一个简单的实现。它非常易于扩展。

struct DisjointSet {
    vector<int> parent;
    vector<int> size;

    DisjointSet(int maxSize) {
        parent.resize(maxSize);
        size.resize(maxSize);
        for (int i = 0; i < maxSize; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_set(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (size[a] < size[b])
                swap(a, b);
            parent[b] = a;
            size[a] += size[b];
        }
    }
};

以下是使用方法。

void solve() {
    int n;
    cin >> n;
    DisjointSet S(n);  // Initializing with maximum Size
    S.union_set(1, 2);
    S.union_set(3, 7);
    int parent = S.find_set(1);  // root of 1
}

- Appaji Chintimi

Answer 3

使用树实现不相交集。有两个操作：

1. find_set(x)：获取包含成员 x 的集合的代表，这里的代表是根节点
2. union_set(x,y)：合并包含成员 x 和 y 的两个集合

树表示法比链表表示法更高效，并采用两种启发式方法： -- “按秩合并”和“路径压缩” --

按秩合并：为每个节点分配秩。秩是节点的高度（节点与后代叶节点之间最长简单路径上的边数）

路径压缩：在“find_set”操作期间，将节点的父节点设为根节点

（参考：《算法导论》第三版，CLRS著）

STL 实现如下：

#include <iostream>
#include <vector>
using namespace std;

struct disjointSet{
    vector<int> parent, rank;
    disjointSet(int n){
        rank.assign(n, 0);
        for (int i = 0; i < n; i++)
            parent.push_back(i);
    }

    int find_set(int v){
        if(parent[v]!=v)
            parent[v] = find_set(parent[v]);
        return parent[v];
    }

    void union_set(int x,int y){
        x = find_set(x);
        y = find_set(y);
        if (rank[x] > rank[y])
            parent[y] = x;
        else{
            parent[x] = y;
            if(rank[x]==rank[y])
                rank[y]++;
        }
    }
};

- Shyju Wilson

---

请阅读：为什么不应该#include <bits/stdc++.h>? 然后（至少）更新你的答案以包含适当的标准头文件。 - Adrian Mole