【算法】并查集

并查集是一种树形的数据结构，通常可以用于高效的合并多个集合和查询两个数是否属于同一个集合的情况。

其原理在于，把每个集合变成一棵树，树根的值就是整个集合的编号，通过查找两个数所在树根是否相同即可判断是否在同一个集合；将树根之间相连即可实现集合的合并。

其合并集合的效率远远高出普通的方式，近似O(1)

但是，集合怎么能变成树呢？为什么用这种结构效率很高呢？

我们以下面这道题为例

该题中提供了两种操作：合并区间和查询两个数是否在同一个集合中

根据题意我们知道一共有n个数，分别是1~n，最开始每个数独自存在一个集合中

虽然说是将集合变成树，实际上我们并不是在物理结构上真正的创建了一棵树，而是通过创建一个数组来存储每个节点的父亲，用该数组来连接不同的数形成树的结构，树根的父亲就是自己。

通过这种形式，我们就可以在数组中查询某个数的父亲，如果查询的结果正好等于该数，说明为根，否则不为根

光这么说不好理解，我们以上面的输入样例为例子，n为4，1~4分别代表4个集合，我们创建一个数组p来存储每个节点的父亲。

此时4个集合中都只有根节点，而我们要将根节点的父亲设置为自己，所以p[1]=1，p[2]=2，以此类推

具体代码为

for(int i = 1;i <= n;i++)
    p[i] = i;

接着看下一行的输入，M 1 2说明将1和2所在的集合合并，我们需要写一个find函数来找到这两个数的根，接着我们直接把1所在集合的根连接到2所在集合的根，即可完成集合的合并

find函数：

int find(int x) //找根节点+路径压缩
{
    if(p[x] != x) p[x] = find(p[x]); //优化：可以将路径上经过的数的父亲全部修改成根
    return p[x];
}

合并操作：

char c;
int a, b;
cin >> c >> a >> b;
if(c == 'M') p[find(a)] = find(b); //根节点相连--合并集合

就像图中这样，只需要将两棵树的根相连，就完成了集合的合并，复杂度为O(1)

（图中所画的树与题目无关） 

所以我们只需通过数组p就能逐步找到根节点并连接，就完成了集合的合并操作

接着我们跳到第四行输入，Q 1 2，也就是询问1和2是否在同一个集合中

对于该操作，我们直接使用find函数找到二者所在集合的根，如果根相等即为同一个集合

完整代码：

#include <iostream>
using namespace std;
#define N 100010
 
int n,m;
int p[N];
 
int find(int x) //找根节点+路径压缩
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
 
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        p[i] = i; //根的父节点=自己
    for(int i = 0;i < m;i++)
    {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if(c == 'M') p[find(a)] = find(b); //根节点相连--合并集合
        else
        {
            if(find(a) == find(b)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    return 0;
}