并查集.md

• 并查集理论基础
• 并查集题型
  • Acwing.836 合并集合
  • Acwing.837 连通块中点的数量
  • leetcode.684 冗余连接

---

并查集理论基础

1. 并查集是一种用于管理元素所属集合的数据结构，其中每棵树表示一个集合，树中的节点表示对应集合中的元素，每棵树的根节点表示当前集合所在的编号
2. 并查集支持两种操作：
   • 合并两个元素所在的集合
   • 查询某个元素所在的集合编号
3. 核心操作 $find$ 函数功能：找到 $x$ 的集合编号，本质是递归的过程

int find(int x){
    // 如果当前节点不是祖宗节点，则递归找到当前节点的祖宗节点，即当前节点的集合编号，并返回
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

并查集题型

Acwing.836 合并集合

• 链接https://www.acwing.com/problem/content/838/

一共有 $n$ 个数，编号是 $1∼n$ ，最开始每个数各自在一个集合中。

现在要进行 $m$ 个操作，操作共有两种：

1. M a b，将编号为 $a$ 和 $b$ 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作
2. Q a b，询问编号为 $a$ 和 $b$ 的两个数是否在同一个集合中

输入格式
第一行输入整数 $n$ 和 $m$

接下来 $m$ 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种

输出格式
对于每个询问指令 Q a b，都要输出一个结果，如果 $a$ 和 $b$ 在同一集合内，则输出 $Yes$，否则输出 $No$。

每个结果占一行。

数据范围
$1 ≤ n$, $m ≤ 10^5$

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

Yes
No
Yes

• 解题代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int p[N];

int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}


int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) p[i] = i;// 初始化
    
    while (m --){
        char op;
        int a, b;
        cin >> op >> a >> b;
        
        if (op == 'M'){
            p[find(a)] = find(b);
        }
        
        else if (op == 'Q'){
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    
    return 0;
}

Acwing.837 连通块中点的数量

• 链接https://www.acwing.com/problem/content/839/

给定一个包含 $n$ 个点（编号为 $1∼n$）的无向图，初始时图中没有边。

现在要进行 $m$ 个操作，操作共有三种：

1. C a b，在点 $a$ 和点 $b$ 之间连一条边，$a$ 和 $b$ 可能相等
2. Q1 a b，询问点 $a$ 和点 $b$ 是否在同一个连通块中，$a$ 和 $b$ 可能相等
3. Q2 a，询问点 $a$ 所在连通块中点的数量

输入格式
第一行输入整数 $n$ 和 $m$

接下来 $m$ 行，每行包含一个操作指令，指令为 C a b, Q1 a b 或 Q2 a 中的一种

输出格式
对于每个询问指令 Q1 a b，如果 $a$ 和 $b$ 在同一个连通块中，则输出 $Yes$，否则输出 $No$。

对于每个询问指令 Q2 a，输出一个整数表示点 $a$ 所在连通块中点的数量

每个结果占一行。

数据范围
$1 ≤ n$, $m ≤ 10^5$

输入样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

Yes
2
3

• 解题代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int p[N], cnt[N];

int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++){
        p[i] = i;
        cnt[i] = 1;
    }
    
    while (m --){
        string op;
        int a, b;
        
        cin >> op;
        if (op == "C"){
            cin >> a >> b;

            if (find(a) != find(b)){
                cnt[find(b)] += cnt[find(a)];
                p[find(a)] = find(b);
            }
        }
        
        else if (op == "Q1"){
            cin >> a >> b;
            
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        
        else {
            cin >> a;
            
            cout << cnt[find(a)] << endl;
        }
    }
    
    return 0;
}

leetcode.684 冗余连接

• 链接https://leetcode.cn/problems/redundant-connection/
• leetcode解题代码

class Solution {
public:
    vector<int> p;

    int find(int x){
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        p.resize(n + 1);

        for (int i = 1; i <= n; i ++) p[i] = i;// 初始化

        for (auto e: edges){
            if (find(e[0]) != find(e[1])) p[find(e[0])] = find(e[1]);
            else return e;
        }
        return {};
    }
};