2.2 并查集

功能

• 将两个集合合并
• 询问两个元素是否在一个集合当中

基本原理

• 每个集合用一棵树来表示
• 树的编号就是整个集合的编号
• 每个节点存储它的父节点，p[x] 表示x的父节点

问题

• 如何判断树根： if(p[x] == x)
• 如何求x的集合编号：while(p[x] != x) x = p[x];
• 如何合并两个集合：(p[x] 是x的集合编号，p[y]是y的集合编号。)p[x] = y

优化

• 路径压缩 : 遍历过的节点都加到根节点下面

代码

//核心代码
int find(int x) {// 返回x的祖宗节点（加上路径压缩
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}`

//题目836
#include<iostream>
using namespace std;

const int N = 100010;

int p[N]; //存每个元素父节点 p[x] = x ,x 是树根

int find(int x) {// 返回x的祖宗节点(加上路径压缩)
    if(p[x] != x) p[x] = find(p[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[0] == 'M') p[find(a)] = find(b);
        else {
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}