合并集合
一共有n个数,编号是1~n,最开始每个数各自在一个集合中。
现在要进行m个操作,操作共有两种:
“M a b”,将编号为a和b的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;
“Q a b”,询问编号为a和b的两个数是否在同一个集合中;
输入格式
第一行输入整数n和m。
接下来m行,每行包含一个操作指令,指令为“M a b”或“Q a b”中的一种。
输出格式
对于每个询问指令”Q a b”,都要输出一个结果,如果a和b在同一集合内,则输出“Yes”,否则输出“No”。
每个结果占一行。
数据范围
1≤n,m≤105
输入样例:
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例:
Yes
No
Yes
C++ 代码
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
/*
本题考察并查集;
由于是对数组元素的单向索引信息进行管理,
因此可以使用一维数组进行存储;
注意两点:
1. 递归操作中一定要设计简化搜索链的行为,
因为完整的拓扑结构可能会有上万层,导致栈溢出;
2. 并查集模型中,仅关心当前元素的最远古祖先,
故无需建立完整的拓扑索引链
*/
const int SIZE = 100005;
int p[SIZE]; // 记录不同数值对应的 parent 关系;
// 查找某数值的最 古老祖先;
int searchRoot(int x) {
int root = x;
// 参与输入的所有数字均大于0,检索到0 意为到达血脉边界;
if (p[x] == x) return x;
// 否则继续追问上一层祖先;
p[x] = searchRoot(p[x]);
// 返回最终查询的祖先值;
return p[x];
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < SIZE; i++) p[i] = i;
char c;
int a, b;
for (int i = 0; i < m; i++) {
cin >> c;
scanf("%d %d", &a, &b);
// M 操作:在 ab 之间建立联系;
// 如此维护,使得同一个集合的元素有共同的最古老祖先;
if (c == 'M') {
p[searchRoot(b)] = searchRoot(a);
}
else if (c == 'Q') {
// 最古老 祖先相同;
if (searchRoot(a) == searchRoot(b)) {
printf("Yes\n");
}
else {
printf("No\n");
}
}
}
return 0;
}