P3367 【模板】并查集

发表于 更新于

P3367 【模板】并查集

题目背景

本题数据范围已经更新到 $1\le N\le 2\times 10^5$，$1\le M\le 10^6$。

题目描述

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

输入格式

第一行包含两个整数 $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

1
2
3
4
5
6
7
8
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出 #1

1
2
3
4
N
Y
N
Y

说明/提示

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

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

对于 $50\%$ 的数据，$1\le N \le 10^4$，$1\le M \le 2\times 10^5$。

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

思路分析 + 代码实现

并查集模板。 $parent$ 数组简写为 $fa$ 。

优化1：迭代路径压缩

1
2
3
4
5
6
7
int find(int x) {
    while (fa[x] != x) {
        fa[x] = fa[fa[x]]; // 将x的父节点指向祖父节点
        x = fa[x]; // 继续向上查找
    }
    return x;
}

递归版本

1
2
3
4
int find(int x) {
    if (x == fa[x]) return x;
    return x = find(fa[x]);
}

优化2：按秩合并

用 $rk$ （即 $rank$ ）记录集合的秩（树的高度上界），令 $fx$ 为秩更小的一方，将 $fx$ 合并到 $fy$ 下，并更新 $fy$ 的秩。

1
2
3
4
5
6
7
void unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return; // 已在同一集合
    if (rk[fx] > rk[fy]) swap(fx, fy);
    rk[fy] = max(rk[fy], rk[fx] + 1);
    fa[fx] = fy;
}

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 2e5 + 5;
int fa[MAXN], rk[MAXN];
int find(int x) {
    while (fa[x] != x) {
        fa[x] = fa[fa[x]];
        x = fa[x];
    }
    return x;
}
void unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return; 
    if (rk[fx] > rk[fy]) swap(fx, fy);
    rk[fy] = max(rk[fy], rk[fx] + 1);
    fa[fx] = fy;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, z, x, y;
    cin >> N >> M;  
    for(int i = 1; i <= N; i++)
        fa[i] = i; // 每个元素初始时父节点是自己
    while (M--) {
        cin >> z >> x >> y;
        if (z == 1) unite(x, y);
        else puts(find(x) == find(y) ? "Y" : "N");
    }
    return 0;
}

常见错误：

  1. 未初始化：忘记将每个元素的父节点初始化为自身。

  2. 混淆合并顺序：在按秩合并时，应确保将秩小的树合并到秩大的树下。