优化并查集（不相交集合）实现

Question

我已经在C ++中为Kattis问题实现了不相交集合联合。然而，我的解决方案效率低下，因为我在第一个隐藏的测试用例中得到TLA（时间限制超出）。有人能发现我的代码中的低效吗？

我基于这篇文章实现了我的代码。特别是，在设置集合的父元素时，我将较小集合的父元素的父元素设置为较大集合的父元素（在进行集合联合时）。根据上述文章，这应该与使用秩一样有效：

两种优化在时间和空间复杂度方面是等效的。因此，在实践中，您可以使用任何一种。

#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;
    }
  }
}

- Bart Louwers

Answer 1

这似乎是一个Kattis特定的IO问题。在main函数开头添加ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);，并将两个endl改为'\n'，可以使其在0.2秒内通过。

我还要提到，包含<bits/stdc++.h> 在这里不被赞同，但你错误的唯一原因是IO。您的并查集实现是正确的，并且在标准逆阿克曼时间界限内运行。

- kcsquared

---

啊，好的，我读了这段代码，使用路径压缩的并查集看起来是正确的。我有一种预感这是一个输入输出问题，但我对 C++ 不是很熟悉。谢谢你澄清了这一点。 - user1984

@user1984 这一点并不明显，只有在排除了所有其他可能性后才发现。我真的以为出现了无限循环；我的建议是，在在线评测机上避免使用像 while (q--) 这样的东西，因为程序的输入和输出都对你隐藏。 - kcsquared

谢谢！我会将第一个报告为错误。我没有想到 std:endl 会有这么大的区别，但我应该知道得更清楚。此外，在竞赛编程中，使用头文件的“hack”实际上是一种推荐做法（但在软件工程中显然不是）。 - Bart Louwers