更新于 

Union Find 并查集

一共有 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≤1051\leq n, m \leq 10^{5}

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

Yes

No

Yes

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int p[N];

// 找到 x 的集合编号
int find(int x) {
  if (p[x] != x)        // 只有集合顶点的 p[x] == x
    p[x] = find(p[x]);  // 因为从属同一个集合,p[x] 的集合编号也是 x 的集合编号,
                        // 查询时也对 x 进行了路径压缩,下次可以用 p[x] 找到它的集合编号
  return p[x];
}


int main() {
  int n, m, a, b;
  char op;
  scanf("%d %d", &n, &m);

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

  // m 个操作
  for (int i = 0; i < m; ++i) {
    scanf(" %c %d %d", &op, &a, &b);
    if (op == 'M') {
// 重复计算两次 find(a) 和 find(b),效率低
//      if (find(a) == find(b))
//        continue;
//      else
//        p[find(a)] = find(b);

      // 合并两个集合
      p[find(a)] = find(b);
    } else if (op == 'Q') {
      // 为什么不直接用 p[a] == p[b] 进行判断,因为没有经历过查询的结点不会进行路径压缩
      // 所以未查询的结点不会被直接挂到编号结点之下,不能直接用 p[a] 查询它的集合编号
      if (find(a) == find(b)) printf("Yes\n");
      else printf("No\n");
    }
  }

  return 0;
}