优化并集查找（Disjoint Set Union）实现

Question

我已经在 C++ 中为 Kattis problem 实现了一个不相交集并集。但是，我的解决方案效率低下，因为我得到了第一个隐藏测试用例的 TLA（超出时间限制）。谁能发现我的代码效率低下？

我的实现基于 this article。特别是，我将较小集合的父集合的父集合设置为较大集合的父集合（当对集合进行并集时）。根据提到的文章，这应该与使用等级一样有效：

Both optimizations are equivalent in terms of time and space complexity. So in practice you can use any of them.

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

class UnionFind {
private:
  vi p;
  vi size;

public:
  UnionFind(int N) {
    p.assign(N, 0);
    for (int i = 0; i != N; ++i)
      p[i] = i;
    size.assign(N, 1);
  }

  int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }

  bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }

  void unionSet(int i, int j) {
    int x = findSet(i);
    int y = findSet(j);
    if (x == y)
      return;
    if (size[x] < size[y])
      swap(x, y);
    p[y] = x;
    size[x] += size[y];
  }
};

int main() {
  int n;
  int q;
  cin >> n >> q;
  auto set = UnionFind(n);
  while (q--) {
    char ch;
    cin >> ch;
    int x;
    int y;
    cin >> x >> y;
    if (ch == '=') {
      set.unionSet(x, y);
    } else if (ch == '?') {
      if (set.isSameSet(x, y))
        cout << "yes" << endl;
      else
        cout << "no" << endl;
    }
  }
}

Answer 1

这似乎是一个 Kattis-specific IO 问题。将 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 添加到 main 的开头，并将两次出现的 endl 更改为 '\n' 会导致它在 .2 秒内通过。

我还要提到在这里不受欢迎，但导致错误的唯一原因是 IO。您的 Union Find 实现是正确的，并且在标准的逆阿克曼时间范围内运行。

优化并集查找（Disjoint Set Union）实现

Optimize Union Find (Disjoint Set Union) implementation

c++

algorithm

disjoint-sets

union-find