Acwing 836. 合并集合

题目描述

思路讲解

并查集：代码短，思路精巧，面试常见。
近乎O（1）的时间复杂度。

代码展示

#include

using namespace std;

const int N = 100010;
int p[N];//定义多个集合

int find(int x) { //返回x的祖宗节点 + 路径压缩
    if (p[x] != x) p[x] = find(p[x]);
    /*
    经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:
    p[x]=x;
    */
    return p[x];
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) p[i] = i;
    while (m--) {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'M') p[find(a)] = find(b);  //集合合并操作
        else if (find(a) == find(b))
            //如果祖宗节点一样,就输出yes
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}
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