废话不多说，我们直接步入正题
目录

1、什么是并查集及并查集的主要作用
2、并查集的基本原理
3、一些比较重要的问题
4、题目：合并集合

1、什么是并查集与并查集的主要作用

你可能经常碰到这两个问题：
1.用数组存储每个元素属于哪个集合；
2.询问两个元素是否在一个集合中；
3.将两个集合合并。

用暴力比较多的同学可能会察觉到，前两个问题其实很简单：

1.belong[x]=a;
2.if(belong[x)==belong[y])

但第三个问题就显得有些难了。
如果一个集合是1000个节点，另一个是2000这种阴间数据已出
现，那起码就要计算1000次左右，所耗时长更不用多说了，但
是如果用并查集做第三题，时间复杂度几乎就是O(1)。
可以说并查集是用来优化暴力的。

2.并查集的一些个基本原理

并查集的基本原理解释起来很简单：
每一个集合都用一棵树表示，而且根的编号就是集合的编号。
每个节点都会存储它的父节点，例如 p[x] 就表示 x 的父节点。

3.关于并查集的一些杂碎问题

Q：如何判断一个节点是不是树根呢？
A：p[x]==x 原因是除根之外，p[x] 都不等于 x。

Q：如何求 x 的集合编号呢？
A：while(p[x]!=x) x=p[x];

Q：如何合并两个集合？
A：将某一树放在另一树某个位置即可，p[x]=y;

Q：如何找出一个节点的所有集合？
A：找那个节点的爹，再判断他爹是不是树根，如果是就返回，不
是就找它爷爷……（爸爸的爸爸叫爷爷～）。

4.题目：合并集合

题目描述

一共有 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

算法：并查集

时间复杂度 $O(1)$

@[无主函数，请自行构思main，QAQ]

朴素并查集（土）

#include <bits/stdc++.h>    //无敌的万能头

using namespace std;    //调用 c++ 功能库

const int N = 100010;   //大小限制

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

int find(int x) //返回 x 的祖宗节点
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
//初始化，假定节点编号是1～n
for(int i=0;i<=n;i++)   p[i]=i;
//合并a和b所在的两个集合
p[find(a)]=find(b);

维护size的并查集（雾）

#include <bits/stdc++.h>    //无敌的万能头

using namespace std;    //调用 c++ 功能库

const int N = 100010;   //大小限制

int p[N],size[N];
//p[]存储每个点的祖宗节点，size[]只有祖宗节
//点的有意义，表示祖宗节点所在集合中点的数量
int find(int x)//返回 x 的祖宗节点
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
//初始化，假定节点编号是1～n
for(int i=0;i<=n;i++)  
{
    p[i]=i;
    size[i]=1;
}
//合并a和b所在的两个集合
size[find(b)]+=size[find(a)];
p[find(a)]=find(b);

维护到祖宗节点的并查集（笑）

int p[N],d[N];
//p[]存储每个点的祖宗节点，d[x] 储存 x 到 p[x] 的距离。
int find(int x)//返回 x 的祖宗节点
{
    if(p[x]!=x)
    {
        int u=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=u;
    }
    //初始化，假定节点编号是1～n
    for(int i=0;i<=n;i++)
    {
        p[i]=i;
        d[i]=0;d
    }
    //合并a和b所在的两个集合
    p[find(a)]=find(b);
    d[find(a)]=distance;//根据具体问题，初始化find(a)的偏移量
}

来都来了，制作不易，顶一下再走吧