合并集合

$($朴素$)$并查集概述

先说朴素并查集，后面还会拓展维护额外信息的并查集
之后的两道题是维护集合大小的并查集与维护到祖宗节点距离的并查集

并查集有路径压缩与按秩合并两种操作，不过我们一般只会用到路径压缩

路径压缩的并查集可以以近乎$O(1)$的时间来完成查询与合并操作

并查集初始化

int p[N]

for (int i = 1; i <= n; i ++ ) p[i] = i;

$p[N]$表示的是某一个结点所在集合的代表元素的下标(或者说是父节点，没有父节点的结点存自己下标)
初始化时候，每个结点是一个独立的集合，而每个集合的代表元素都是自己

并查集的常见操作

1. 寻找祖宗结点

这里可以同时进行路径压缩，之前的画出来的树，是很多结点依次指向直接父节点，路径压缩后，每个结点的父节点都会是祖宗结点，减少了下一次查询与合并的时间

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]); // 每一个p[x]最后都会赋值为它的祖宗结点下标，即完成了路径压缩
    return p[x];
}

2. 合并a和b所在的两个集合

让$a$集合的祖宗结点（代表元素）的父节点设置为$b$集合的祖宗结点

p[find(a)] = find(b);

代码

#include <iostream>

using namespace std;

const int N = 100010;

int p[N];

int find(int 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 == 'M') p[find(a)] = find(b); //合并操作
        else
        {
            if (find(a) == find(b)) puts("Yes"); //查询祖宗结点
            else puts("No");
        }
    }

    return 0;
}