acwing 836. 合并集合

1. 朴素并查集：

int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;

// 合并a和b所在的两个集合：
p[find(a)] = find(b);

大致思路

开始时每个集合都是一个独立的集合,并且都是等于自己本身下标的数
例如:
p[5]=5,p[3]=3;
如果是M操作的话那么就将集合进行合并,合并的操作是:
p[3]=p[5]=5;
所以3的祖宗节点便成为了5，此时以5为祖宗节点的集合为{5，3}如果要将p[9]=9插入到p[3]当中,应该找到3的祖宗节点,然后再把p[9]=9插入其中,所以p[9]=find(3);(find()函数用于查找祖宗节点)也可以是p[find(9)]=find(3),因为9的节点本身就是9此时以5为祖宗节点的集合为{5,3,9}。如果碰到多个数的集合插入另一个集合当中其原理是相同的。

例如:
上述中以5为祖宗节点的是p[5],p[3],p[9];(即p[5]=5,p[3]=5,p[9]=5)
再构造一个以6为祖宗节点的集合为{6,4，7，10}，如果要将以6为祖宗节点的集合插入到以5为祖宗节点的集合,则该操作可以是p[6]=find(3)（或者find(9),find(5)），此时p[6]=5，当然如果是以6为祖宗节点集合中的4,7,10则可以这样p[find(4)]=find(3)或者p[find(7)]=find(3)均可以，此时以6为祖宗节点的集合的祖宗节点都成为了5。

例题

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

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

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

输入

第一行输入整数n和m。
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
接下来m行，每行包含一个操作指令，指令为“M a b”或“Q a b”中的一种。

输出

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

每个结果占一行。
Yes
No
Yes

代码

#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,a,b;
char op[2];
int p[N];
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    while(m--){
        scanf("%s%d%d",op,&a,&b);
        if(op[0]=='Q'){
            if(find(a)==find(b))puts("Yes");
            else puts("No");
        }else p[find(a)]=find(b);
    }

    return 0;
}