当前位置：首页 > article >正文

并查集：合并集合

article 2025/1/8 14:13:05

题目描述

问题描述：有 n 个数，编号为 1∼n，初始时每个数在一个单独的集合中。进行 m 个操作，操作分为两种：
1. M a b：合并编号为 a 和 b 的两个数所在的集合。
2. Q a b：询问编号为 a 和 b 的两个数是否在同一个集合中。
输入格式：
- 第一行输入整数 n 和 m。
- 接下来 m 行，每行包含一个操作指令。
输出格式：
- 对于每个询问指令 Q a b，输出 Yes 或 No。
数据范围：1≤n,m≤1051≤n,m≤105。
输入样例：
```
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 = 1e6 + 10;
int e[N], n, m;
int find(int x)
{
	if (e[x] != x) //如果这个数的父节点不等于本身，就继续寻找这个数的祖宗
	{
		find(e[x]);
	}
	return e[x];
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		e[i] = i; //最开始1~n每个数都属于一个集合
	}
	char c;
	int a, b;
	while (m--)
	{
		cin >> c;
		if (c == 'M')
		{
			cin >> a >> b;
			if (find(a) != find(b)) //如果这两个数的祖宗结点不是一个（及不在一个集合）
			{
				e[find(a)] = find(b); //就让a的祖宗结点指向b的祖宗结点
			}
		}
		else
		{
			cin >> a >> b;
			if (find(a) == find(b)) //如果两个在一个集合
				cout << "yes" << endl;
			else
				cout << "no" << endl;
		}
	}
	return 0;
}

代码总结

1. 问题背景

有 n 个数，编号为 1∼n，初始时每个数在一个单独的集合中。
需要进行 mm 个操作，操作分为两种：
1. 合并操作（M a b）：将编号为 a 和 b 的两个数所在的集合合并。
2. 查询操作（Q a b）：询问编号为 a 和 b 的两个数是否在同一个集合中。

2. 数据结构设计

使用一个数组 e[N] 来表示每个元素的父节点。
- 初始时，e[i] = i，表示每个元素自己是一个集合的根节点。
通过 路径压缩 和 合并操作 来优化集合的查找和合并效率。

3. 核心操作

(1) 查找操作（`find` 函数）

功能：查找某个元素所在集合的根节点（代表元素）。
实现：
- 如果当前元素的父节点不是它自己，递归地查找其父节点的根节点。
- 返回根节点。

代码：

int find(int x) {
    if (e[x] != x) { // 如果当前节点的父节点不是自己
        find(e[x]);  // 递归查找根节点
    }
    return e[x];     // 返回根节点
}

优化：
- 当前代码没有进行路径压缩，效率较低。
- 可以通过路径压缩优化，将查找路径上的所有节点直接指向根节点：
```
int find(int x) {
    if (e[x] != x) {
        e[x] = find(e[x]); // 路径压缩
    }
    return e[x];
}
```

(2) 合并操作（`M a b`）

功能：将两个元素所在的集合合并。
实现：
- 查找 a 和 b 的根节点。
- 如果根节点不同，将 a 的根节点指向 b 的根节点。

代码：

if (find(a) != find(b)) { // 如果 a 和 b 不在同一个集合
    e[find(a)] = find(b); // 将 a 的根节点指向 b 的根节点
}

优化：
- 可以使用 按秩合并（将较小的树合并到较大的树中），以保持树的平衡，进一步优化性能。

(3) 查询操作（`Q a b`）

功能：查询两个元素是否在同一个集合中。
实现：
- 查找 a 和 b 的根节点。
- 如果根节点相同，输出 Yes，否则输出 No。

代码：

if (find(a) == find(b)) { // 如果 a 和 b 在同一个集合
    cout << "Yes" << endl;
} else {
    cout << "No" << endl;
}

4. 代码流程

初始化：

读取 n* 和 m。
初始化 e[N] 数组，使每个元素的父节点指向自己。

for (int i = 1; i <= n; i++) {
    e[i] = i; // 每个元素自己是一个集合
}

处理操作：

对于每个操作：
- 如果是合并操作（M a b），调用 find 函数查找 a 和 b 的根节点，并进行合并。
- 如果是查询操作（Q a b），调用 find 函数查找 a 和 b 的根节点，并输出结果。

while (m--) {
    cin >> c;
    if (c == 'M') {
        cin >> a >> b;
        if (find(a) != find(b)) {
            e[find(a)] = find(b); // 合并集合
        }
    } else {
        cin >> a >> b;
        if (find(a) == find(b)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}