并查集

1 概念

并查集是一种可以动态维护若干不重叠的集合，并且支持合并与查询的数据结构，也就是擅长维护各种各样的具有传递性质的关系。

说人话，并查集提供两个功能：

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

2 基本原理

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

问题：

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

3 具体实现

使用树形结构存储每个集合，刚开始时每个点就是一个独立的集合，且这个集合树的树根就是本身

void init(int n) 
{
    for (int i = 1; i <= n; i ++)
        p[i] = i;
}
// p数组为这个点的父亲,刚开始也就是树根祖宗

find()

路径压缩：每执行一次 find() 操作时，把访问过的节点(也就是所有元素的父亲),都统统指向树根祖宗。

int find(int x)
{
    while(p[x] != x) {
        p[x] = find(p[x]);   // 路径压缩， x的父节点指向祖宗节点
    }
    return p[x];
}
// 返回 x 的祖宗节点

merge()

void merge(int x, int y) 
{
    p[find(x)] = find(y);
}
// x 的祖宗节点的父节点等于y的祖宗节点

4 模板

void init(int n)
{
    for (int i = 1; i <= n; i ++) {
        p[i] = i;
    }
}

int find(int x)
{
    while(p[x] != x) {
        p[x] = find(p[x]);
    }
    return p[x];
}

void merge(int x, int y)
{
    p[find(x)] = find(y);
}

5 题目

合并集合

#include <bits/stdc++.h>
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;
}