题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 $N,M$ ,表示共有 $N$ 个元素和 $M$ 个操作。

接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ 。

当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。

当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出
Y ；否则输出 N 。

输出格式

对于每一个 $Z_i=2$ 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

样例 #1

样例输入 #1

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

样例输出 #1

N
Y
N
Y

提示

对于 $30\%$ 的数据，$N \le 10$，$M \le 20$。

对于 $70\%$ 的数据，$N \le 100$，$M \le 10^3$。

对于 $100\%$ 的数据，$1\le N \le 10^4$，$1\le M \le 2\times 10^5$，$1 \le X_i, Y_i \le N$，$Z_i \in { 1, 2 }$。

解答：

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

struct dsu {
  vector<size_t> pa, size;

  explicit dsu(size_t size_) : pa(size_), size(size_, 1) {
    for (int i = 0; i < pa.size(); i++) {
        pa[i] = i;
    }
  }

  //路径压缩 
  size_t find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }

  //启发式合并 
  void unite(size_t x, size_t y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (size[x] < size[y]) swap(x, y);
    pa[y] = x;
    size[x] += size[y];
  }
};

int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    dsu my_dsu = dsu(n);
    for (int i = 0; i < m; i++) {
        int z,x,y;
        cin >> z >> x >> y;
        if (z == 1) {
            my_dsu.unite(x, y);
        } else {
            if (my_dsu.find(x) == my_dsu.find(y)) {
                cout << "Y" << endl;
            } else {
                cout << "N" << endl;
            }
        }
    }
    return 0;
}

同时使用路径压缩和启发式合并之后，并查集的每个操作平均时间仅为 O(\alpha(n))，其中 \alpha 为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。

参考：

1. https://oi.wiki/ds/dsu/
2. https://www.luogu.com.cn/problem/P3367