并查集详解

什么是并查集

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这是百度百科的定义，说人话就是并查集可以高效的合并两个集合以及查找两个元素是否在一个集合中

所以并查集通常包含两中操作

        查找：查询两个元素是否在同一个集合

        合并：将两个集合合并

并查集适用问题 

我们这里用一个数组belong[x]存储每个节点的集合编号来表示这个节点在那一个集合当中，查找操作直接判断belong[x]==belong[y]即可，O(1)的时间复杂度。但是合并操作就不是很容易了，如果两个集合的元素都非常多的话，我们将一个集合的所有元素的集合编号都改成另一个集合的话这样非常耗时间

比如集合1有3000个元素，集合2有5000个元素，我们将集合1合并到集合2，我们要将集合1的3000个元素的集合编号改成集合2，这样暴力维护这两个集合是非常耗时的，它不是O(1)的复杂度。所以并查集可以解决这个难题。并查集可以在近乎O(1)的复杂度完成这两个操作。

所以需要用到这两个操作的时候就可以用并查集来解决。

并查集基本原理

并查集是一种树型的结构，每一个集合用一颗树表示，不一定是二叉树，树根的编号就是整个集合的编号，每个子节点存储它的父节点，这里用p[x]表示x的父节点

 开始时每个元素各自是一个集合也就是p[x]=x，在不断的集合合并之后，只有每个集合的根节点还是P[x]=x,其他的节点p[y]!=y，p[y]都等于父节点的编号了。其中在不断的集合合并的过程中还需要用到一个路径压缩优化，这个后面讲，不然这个复杂度还是很高。

需要解决的问题

问题1：如何判断树根:if(p[x]==x)

        上面也说过了，除了根节点之外p[x]都不等于x

问题2：如何求x的集合编号：while(p[x]!=x) x=p[x]

        只要x不是树根，就一直往上走，直到走到树根为止，最后x的值就是集合的编号

问题3：如何合并两个集合：p[x]是x的集合编号，p[y]是y的集合编号，合并直接p[x]=y

        直接把某一个树直接插到另一个树的某一个位置就可以了，这里直接把一个集合的 根节点指向另一个集合的根节点，这样一个集合就成了另一个集合的子树了。

路径压缩优化

解决完上面的问题，时间复杂度还是很高，因为在问题2那里我们求x的集合编号，我们每次都要从当前节点遍历到根节点，遍历的次数和树的高度是成正比的，也就是说树的高度也高，我们遍历的次数越多。在不断的集合合并之后，树的高度可能会非常高，这样就需要遍历很多次，复杂度太高。

所以这里就有一个路径压缩优化，这个就是并查集的核心，优化之后并查集的速度就会非常快了。

路径压缩优化就是在找x节点的根节点时，让这一条路径上的所有经过的点都指向根节点 

 这样只要搜一遍就可以把路径上的点都指向根节点，一步到位。这样我们求完x的根节点之后，我们再求x的根节点这样就只需要走一次了。

这里我们用递归实现路径压缩同时返回根节点

int find(int x)

{

if(p[x]!=x) p[x] = find(p[x]);  //一直递归到根节点然后回溯，回溯的过程就是路径压缩

return p[x];

}

关于并查集的优化还有按秩合并，不过按秩合并的优化并不明显，所以一般并查集是用路径压缩优化，这里就不再说按秩合并了，感兴趣可以去了解一下。

例题-合并集合

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

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

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

输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

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

每个结果占一行。

数据范围

1≤n,m≤1e5

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

Yes
No
Yes

代码实现

#include <iostream>
using namespace std;
const int N=1e5+10;
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;//开始每个数自己就是一个集合
    }
    while(m--)
    {
        char op;
        int a,b;
        cin>>op;
        cin>>a>>b;
        if(op=='M')
        p[find(a)]=p[find(b)];
        else
        {
            if(p[find(a)]!=p[find(b)])
            cout<<"No"<<endl;
            else
            cout<<"Yes"<<endl;
        }
    }
    return 0;
}

如果错漏之处，敬请指正！