题目描述

给定一堆编号为1到n的数据，支持两个操作：
+ 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

算法1

并查集

并查集支持的操作
1. 将两个集合合并；
2. 查询两个元素是否在同一个集合中；

基本的原理就是将每个集合用一个树来表示，树的根节点编号是每个集合的编号，在每个节点中保存的是它的父节点，在合并时将一棵树合并到另一个树的根节点上，查询时找到每个节点所在的根节点是否相同即可；
+ 并查集的节点可以没有子节点指针，但一定要有父节点指针，所以这样来看其实并查集是一棵逆着的树；
+ 此并查集的查询操作与树的高度是成正比的；
+ 对此并查集，查询某个元素所在的集合的操作是递归查询其父节点，直到根节点；

并查集的优化：
1. 路径压缩：当每次找到根节点后，将此路径上每个元素的父节点指针全部指向根节点，此为O(logn)操作；此优化之后每次查询直接查询到根节点，就是O(1)级操作了；
2. 按秩合并：合并时将较浅的树变成较深的树的字数

C++ 代码

#include<iostream>
using namespace std;

int find(int p[], int x){
    if(p[x] != x) p[x] = find(p,p[x]);      //找x集合编号并路径压缩；
    return p[x];
}

int main(){
    ios::sync_with_stdio(false);

    int n, m;
    cin>>n>>m;
    int p[n+1], a, b;
    for(int i = 1; i <= n; ++i) p[i] = i;
    char op;
    while(m--){
        cin>>op>>a>>b;
        if(op == 'M') p[find(p,a)] = find(p,b);
        else cout<<(find(p,a) == find(p,b) ? "Yes" : "No")<<endl;
    }
    return 0;
}