并查集

解决的问题

并查集解决了两个问题：

迅速将两个集合合并成一个集合。
迅速查询两个元素是否在同一集合中。

原理

将一个集合看成一棵树，树根的编号就是整个集合的编号。每一个节点都可以找到自己的父节点，p[x]表示x的父节点。

问题

如何判断树根：p[x] == x。
如何求x的集合编号：while ( p[x] != x ) x = p[x];。
如何合并两个集合：只需要修改其中一个集合根元素的编号就可以了。假设p[x]、p[y]是x、y集合的编号，只需要p[x] = y或者p[y] = x即可。

路径压缩优化

如何一个集合树比较高，查找路径会比较长，最差可退化成 $O(N)$ 。所以在查询的时候，可以将路径中每一个节点直接指向根节点。

这样优化后，查询效率几乎逼近 $O(1)$ 。

问题是如何解决的

修改两个集合中任意一个根节点的值即可。
对于节点x、y，只需判断x、y节点的根节点是否相等即可。

例子

原题链接

题目描述

一共有 $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 \le n,m \le 10^5$ 。

输入样例：

输出样例：

Yes
No
Yes

代码

#include <iostream>
#include <string>

using namespace std;

const int N = 100010;

int p[N], n, m;

int find(int x)
{
    // 涵路径压缩
    return p[x] == x ? p[x] : p[x] = find(p[x]);
}

int main() 
{
    cin >> n >> m;
    for ( int i = 1; i <= n; i ++ )
        p[i] = i;
    
    string op;
    int a, b;
    while ( m -- )
    {
        cin >> op >> a >> b;
        if ( op == "M" ) p[find(a)] = p[find(b)];
        else cout << (p[find(a)] == p[find(b)] ? "Yes" : "No") << endl;
    }
    return 0;
}