题目描述

原题

一共有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≤105
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：
Yes
No
Yes

算法 并查集

并查集作用：

1. 将两个集合合并
   2.询问两个元素是否在一个集合当中
   并查集可以以近乎O（1）的时间复杂度完成这两个操作。

基本原理：

1. 1.每一个集合用一个树（不一定是二叉树）来维护
   2.每一个集合的编号就是当前根结点的编号。
   3.对于每个结点都存储它的父结点，p[x]表示它的父结点
   4.判断一个元素属于哪个集合的时候，我们可以先找到它的父结点看一下是不是树根，如果
   不是，就继续往上找，一直找到树根为止，然后根据树根的编号就可以知道这个元素属于
   哪一个集合。

问题：

1. 判断树根： if(p[x] == x)
   只有树根是等于x的

2. 求x的集合编号： while(p[x] != x) x= p[x];
   只要x不是树根，就一直往上走，直到走到树根为止。求x的集合编号其实就是判断x属于哪
   一个集合里面。
   优化：路径压缩
   假设当前结点a往上找根结点找到的时候，那我们就把往上找的那一条路径上的所有
   结点直接指向根结点，如此就剩下了很多的时间。
   这个优化之后，就可以看成O（1）的时间复杂度。

3. 合并两个集合： px是集合x的集合编号 ， py是集合y的集合编号 P[x] = y;
   就是把x直接插到y树上面去。

参考文献

y总讲解视频

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
//p存储父结点是谁， 初始的时候，每个元素都是一个单独的集合
//所以说每个集合里面只有一个结点，这个结点的元素就是自己
int p[N];
//n个数  m个操作
int n , m;

//返回x的根结点（加上优化的）
int find(int x){
    //如果x不是根结点，就一直递归遍历找下去
    // p[x] = find(p[x])这里就是路径压缩直接，直接指向根结点
    if(p[x] != x) p[x] = find(p[x]);
    //找到 返回根结点
    return p[x];
}

int main(){
    //读入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[0] == 'M'){
            /*find(a)返回a的根结点  find(b)返回b的根结点
              这里直接让a的根结点的父结点变成b的根结点，从而直接插入到另一棵树中
            */
            p[find(a)] = find(b);
        }else{
            //判断两个元素是否在一个集合里面 puts()等价于cout<<endl。也就是输出后自带换行
            if(find(a) == find(b))puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

有按秩合并的

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010 ;

// p表示每个点的父结点 r表示每个树的高度
int p[N] , r[N];
// n表示集合数量；m表示操作数量
int n ,m ;

// 查询某个数
int find(int x){
    // x不是根结点，继续往上查找x父结点的父结点，p[x] = find(p[x])这里就是路径压缩直接，
    // 直接指向根结点
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 按秩合并
void merge( int a , int b){
    // 找到a，b的根结点
    a = find(a) , b = find( b );
    // 在同一个集合中就不用了操作了,也就是看其根结点是不是同一个
    if( a == b ) return;

    // 判断哪个树的高度更高,矮树插入到高树中
    if( r[a] > r[b] ) p[b] = a;//b的父结点是a，b树插入a树中
    else{
        // b树高，a树插入到b树中
        p[a] = b;
        // 两树高度相同,随便把一个树插入到另外一个树中，高度会多1 
        if( r[a] == r[b] ) r[b] ++;
    }


}

int main(){
    scanf("%d%d" , &n , &m);

    //先初始化每个集合,并查集
    for(int i = 1 ; i <= n ; i++){
        //最开始每个数都是一个单独的集合
        p[i] = i;
        //每个树的高度是1
        r[i] = 1 ;

    }

    //m个操作
    while(m--){
        // 用字符串读字母好处是可以过滤掉空格和回车
        char op[2];

        int a , b;
        scanf("%s%d%d" , op , &a, &b);
        // 合并操作
        if(op[0] == 'M')merge(a , b);
        else{//查询操作
        // 两个是在同一个树中即在同一个集合中
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}