[//]: # (推荐题解模板,请替换blablabla等内容 ^^
过程模拟:
输入:4 5
初始化并查集,每个元素都是自己的祖宗节点,p = [0, 1, 2, 3, 4]
执行第一个操作:M 1 2
合并元素1所在集合的祖宗节点为元素2所在集合的祖宗节点,p = [0, 2, 2, 3, 4]
执行第二个操作:M 3 4
合并元素3所在集合的祖宗节点为元素4所在集合的祖宗节点,p = [0, 2, 2, 4, 4]
执行第三个操作:Q 1 2
查询元素1和元素2是否属于同一集合,它们的祖宗节点都是2,因此输出 “Yes”
执行第四个操作:Q 1 3
查询元素1和元素3是否属于同一集合,它们的祖宗节点分别是2和2,因此输出 “No”
执行第五个操作:Q 3 4
查询元素3和元素4是否属于同一集合,它们的祖宗节点都是4,因此输出 “Yes”
C++ 代码
#include<iostream>
using namespace std;
const int N = 100010; // 定义常量 N,表示并查集数组的最大大小
int n, m; // n 表示元素个数,m 表示操作个数
int p[N]; // 并查集数组,用于存储元素所在的集合
// find 函数用于查找 x 所在的集合,同时进行路径压缩
int find(int x) {
if (p[x] != x) p[x] = find(p[x]); // 路径压缩:将 x 的祖宗节点设为 x 所在集合的祖宗节点
return p[x]; // 返回 x 所在集合的祖宗节点
}
int main() {
scanf("%d%d", &n, &m); // 读取 n 和 m 的值
// 初始化并查集,每个元素初始时都是自己的祖宗节点
for (int i = 0; i <= n; i++) {
p[i] = i; // 将每个元素的祖宗节点初始化为自己
}
while (m--) {
char op[2]; // 操作类型,可以是 'M' 或 'Q'
int a, b; // 操作涉及的两个元素
scanf("%s%d%d", op, &a, &b); // 读取操作类型和两个元素
if (op[0] == 'M') { // 如果操作是合并集合
p[find(a)] = find(b); // 将 a 所在集合的祖宗节点设为 b 所在集合的祖宗节点,实现合并操作
} else { // 如果操作是查询是否属于同一集合
if (find(a) == find(b)) {
puts("Yes"); // 输出 "Yes" 表示 a 和 b 属于同一集合
} else {
puts("No"); // 输出 "No" 表示 a 和 b 不属于同一集合
}
}
}
return 0;
}
JAVA代码
import java.util.Scanner;
public class Main {
static final int N = 100010;
static int[] p = new int[N];
static int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
for (int i = 0; i <= n; i++) {
p[i] = i;
}
while (m-- > 0) {
String op = scanner.next();
int a = scanner.nextInt();
int b = scanner.nextInt();
if (op.equals("M")) {
p[find(a)] = find(b);
} else {
if (find(a) == find(b)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
scanner.close();
}
}