c++ - 并集数据结构

Question

对于许多问题，我认为推荐的解决方案是使用 union 查找数据结构。我试图阅读它并思考它是如何实现的(使用 C++)。我目前的理解是，它只是一个集合列表。所以要找到一个元素属于哪个集合，我们需要 n*log n 操作。而当我们必须执行 union 时，我们必须找到需要合并的两个集合并对其执行 set_union 。这对我来说看起来不是很有效。我对这个数据结构的理解是正确的还是我遗漏了什么？

Answer 1

这是很晚的回复，但可能在 stackoverflow 上的其他地方没有得到回答，并且由于这是搜索 union-find 的人的最顶部页面，这里是详细的解决方案。

Find-Union 是一种非常快速的操作，在几乎恒定的时间内执行。它遵循 Jeremie 对路径压缩和跟踪集大小的见解。对每个查找操作本身执行路径压缩，从而花费摊销的 lg*(n) 时间。 lg* 就像逆阿克曼函数，增长非常缓慢，很少超过 5(至少直到 n< 2^65535)。 union/合并集是惰性执行的，只需将 1 个根指向另一个，特别是较小集的根指向较大集的根，这是在恒定时间内完成的。

引用下面的代码 https://github.com/kartikkukreja/blog-codes/blob/master/src/Union%20Find%20%28Disjoint%20Set%29%20Data%20Structure.cpp

class UF {
  int *id, cnt, *sz;
  public:
// Create an empty union find data structure with N isolated sets.
UF(int N) {
    cnt = N; id = new int[N]; sz = new int[N];
    for (int i = 0; i<N; i++)  id[i] = i, sz[i] = 1; }
~UF() { delete[] id; delete[] sz; }

// Return the id of component corresponding to object p.
int find(int p) {
    int root = p;
    while (root != id[root])    root = id[root];
    while (p != root) { int newp = id[p]; id[p] = root; p = newp; }
    return root;
}
// Replace sets containing x and y with their union.
void merge(int x, int y) {
    int i = find(x); int j = find(y); if (i == j) return;
    // make smaller root point to larger one
    if (sz[i] < sz[j]) { id[i] = j, sz[j] += sz[i]; }
    else { id[j] = i, sz[i] += sz[j]; }
    cnt--;
}
// Are objects x and y in the same set?
bool connected(int x, int y) { return find(x) == find(y); }
// Return the number of disjoint sets.
int count() { return cnt; }
};