在 C++ 中实现等价关系（使用 boost::disjoint_sets）

假设您有许多元素，并且需要跟踪它们之间的等价关系。如果元素A等价于元素B，则它等价于B所等价的所有其他元素。

我正在寻找一种有效的数据结构来编码这些信息。应该可以通过与现有元素的等价来动态添加新元素，并且根据该信息应该可以有效地计算新元素等价的所有元素。

例如，考虑以下元素 [0,1,2,3,4] 的等价集：

0 = 1 = 2
3 = 4

其中等号表示等价。现在我们添加一个新元素5

0 = 1 = 2
3 = 4 
5

并强制执行等效性5=3，数据结构变为

0 = 1 = 2
3 = 4 = 5

由此，人们应该能够有效地迭代任何元素的等价集。对于 5，该集合将为 [3,4,5]。

Boost 已经提供了一个方便的数据结构，称为disjoint_sets这似乎满足了我的大部分要求。考虑这个简单的程序，它说明了如何实现上述示例：

#include <cstdio>
#include <vector>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/unordered/unordered_set.hpp>

/*
    Equivalence relations
    0 = 1 = 2
    3 = 4
 */

int main(int , char* [])
{
    typedef std::vector<int> VecInt;
    typedef boost::unordered_set<int> SetInt;

    VecInt rank (100);
    VecInt parent (100);
    boost::disjoint_sets<int*,int*> ds(&rank[0], &parent[0]);
    SetInt elements;
    for (int i=0; i<5; ++i) {
        ds.make_set(i);
        elements.insert(i);
    }

    ds.union_set(0,1);
    ds.union_set(1,2);
    ds.union_set(3,4);

    printf("Number of sets:\n\t%d\n", (int)ds.count_sets(elements.begin(), elements.end()));

    // normalize set so that parent is always the smallest number
    ds.normalize_sets(elements.begin(), elements.end());
    for (SetInt::const_iterator i = elements.begin(); i != elements.end(); ++i) {
        printf("%d %d\n", *i, ds.find_set(*i));
    }

    return 0;
}

如上所示，我们可以有效地添加元素，并动态扩展不相交的集合。如何有效地迭代单个不相交集合的元素，而不必迭代所有元素？

很可能你做不到，disjoint_sets不支持仅对一组进行迭代。底层的数据结构和算法无论如何都无法有效地完成它，即即使有内置的支持disjoint_sets对于仅在一组上进行迭代，这将与在所有组上进行迭代并过滤掉错误的组一样慢。