题目描述

一共有n个数，编号是1~n，最开始每个数各自在一个集合中。

现在要进行m个操作，操作共有两种：

“M a b”，将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
“Q a b”，询问编号为a和b的两个数是否在同一个集合中；

输入格式

第一行输入整数n和m。

接下来m行，每行包含一个操作指令，指令为“M a b”或“Q a b”中的一种。

输出格式

对于每个询问指令”Q a b”，都要输出一个结果，如果a和b在同一集合内，则输出“Yes”，否则输出“No”。

每个结果占一行。

数据范围

1≤n,m≤10^5

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例

Yes
No
Yes

__

课堂笔记

并查集：
将两个集合合并或者判断两个元素是否在一个集合中
原理：
一个集合一个树表示数根号即整个集合编号。每个节点存父结点！，p[x] 为x的父结点
问题

1. 判断树根
2. 如何求X编号
3. 如何合并 –> 一个集合的祖宗节点的父结点是另一集合的祖宗结点

C++ 代码

#include<iostream>

using namespace std;

const int N = 100010;

int p[N]; //p[]表示数的父结点

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]; // 在C语言中字符串最后一位是\0 可以直接用一个 char 类型 
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (op[0] == 'M') p[find(a)] = find(b); //合并，A数的祖宗节点的父节点为B数的祖宗节点
        else 
        {
            if(find(a) == find(b)) cout << "Yes"<<endl;
            else cout <<"No"<<endl;
        }
    }
    return 0;
}