并查集其实就是巧妙地利用了数组的数据结构和查询划分只需要类这一个属性的特点
，将数组下标（节点）对应到了对应数组保存的值（祖先节点），从而实现归类和查找

并查集基础学习 836. 合并集合

M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No
Yes

这道题并查集可以把一条路径上的节点全部指向祖先节点

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N];

int find(int x)
{
    if (p[x] != x) // 只有祖宗节点的p[x]值等于他自己，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); // p[find(b)] = find(a); 都ok，只是放到同一个父节点
        else if (find(a) == find(b))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

837. 连通块中点的数量

• 思路：考察并查集
• 略

Description

给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：

• C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
• Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
• Q2 a，询问点 a 所在连通块中点的数量；

Input

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2
a中的一种。第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

Output

对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量
每个结果占一行。

1≤n,m≤105

Sample

• Input

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

• Output

Yes
2
3

• Code:

#include <bits/stdc++.h>
using namespace std;
// #define LOCAL
// #define DEBUG
const int N = 1e7 + 10;
int n, m, sum = 0;
int res[N], cnt[N];
bool st[N];
int find(int i)
{
    if (res[i] != i)
    {
        // cnt[res[i]] += cnt[i];
        // cnt[i] = 0; 不需要一个个递归追溯，只需要修改祖先节点即可，复杂反而写错了o`(*>﹏<*)′
        res[i] = find(res[i]);
    }
    return res[i];
}
int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    scanf("%d%d", &n, &m);
    char c[2];
    int a, b;
    for (int i = 0; i < n + 1; i++)
    {
        res[i] = i;
        cnt[i] = 1;
    }
    while (m--)
    {
        scanf("%s%d", c, &a);
        if (*c == 'C')
        {
            scanf("%d", &b);
            // if (a == b) 
            //     continue;
            // res[a] = find(b);
            // find(a); 
            a = find(a), b = find(b);
            if (a != b)
            {
                res[a] = b;
                cnt[b] += cnt[a];
                cnt[a] = 0; // 可以不加，不是祖先节点就不会读取cnt
            }
#ifdef DEBUG
            for (int i = 0; i < n + 1; i++)
                printf("%d ", cnt[i]);
            printf("\n");
#endif
        }
        else if (*c == 'Q')
        {
            if (*(c + 1) == '1')
            {
                scanf("%d", &b);
                if (find(a) == find(b))
                    printf("Yes\n");
                else
                    printf("No\n");
            }
            else if (*(c + 1) == '2')
                printf("%d\n", cnt[find(a)]);
        }
    }
    return 0;
}