信息奥赛｜并查集

知识点概览 🚀

并查集的概念
pre[] 数组的初始化
find() 函数的实现
union()/join() 函数的实现
find() 函数优化——路径压缩
并查集代码模版

知识点详解 🎥

学习素材

编号	内容	链接	平台	创作者	推荐指数
1	【算法与数据结构】—— 并查集	链接1	CSDN	theSerein	必看
2	算法基础课——并查集	链接2	Acwing	大雪菜	（可选）

代码模版

初始化 pre[]

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;

int n, m, a, b;
char op;
int pre[N];

// 并查集初始化，每个元素都是一个集合
void init() {
    for (int i = 1; i <= n; ++i) {
        pre[i] = i;
    }
}

查找 find()

// 查找 + 路径压缩
int find(int x) {
    // 路经压缩是if，不是while
    if (pre[x] != x) pre[x] = find(pre[x]);
    // 下面这行while是错误写法
//    while (pre[x] != x) pre[x] = find(pre[x]);
    // 下面这个写法是无路径压缩的查找，也是正确的
//    while (pre[x] != x) x = pre[x];
    return pre[x]; // 这里必须返回pre[x]，而不是x，因为上面的条件不是while
}

合并 union() / join()

// 合并两个集合
void join(int a, int b) {
    int x = find(a);
    int y = find(b);
    if (x != y) pre[x] = y;
}

查询 query()

// 查询
void query(int a, int b) {
    if (find(a) == find(b))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

完整代码

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;

int n, m, a, b;
char op;
int pre[N];

// 并查集初始化，每个元素都是一个集合
void init() {
    for (int i = 1; i <= n; ++i) {
        pre[i] = i;
    }
}

// 查找 + 路径压缩
int find(int x) {
    // 路经压缩是if，不是while
    if (pre[x] != x) pre[x] = find(pre[x]);
    // 下面这行while是错误写法
//    while (pre[x] != x) pre[x] = find(pre[x]);
    // 下面这个写法是无路径压缩的查找，也是正确的
//    while (pre[x] != x) x = pre[x];
    return pre[x]; // 这里必须返回pre[x]，而不是x，因为上面的条件不是while
}

// 合并两个集合
void join(int a, int b) {
    int x = find(a);
    int y = find(b);
    if (x != y) pre[x] = y;
}

// 查询
void query(int a, int b) {
    if (find(a) == find(b))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n >> m;
    init();  // 初始化并查集
    for (int i = 1; i <= m; ++i) {
        cin >> op >> a >> b;
        if (op == 'M') join(a, b);
        else query(a, b);
    }

    return 0;
}