并查集详解

并查集

并查集（Union-find Sets）是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。

并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。

yxc模板

链接：https://www.acwing.com/blog/content/404/

并查集 —— 模板题:AcWing 836. 合并集合, AcWing 837. 连通块中点的数量

(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[a] = b;

(2)维护size的并查集：

int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

// 返回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;
    size[i] = 1;
}

// 合并a和b所在的两个集合：
a = find(a),b = find(b);// 必须用变量存一下find，否则下面会改变find导致bug
if (find(a) != find(b)){// a,b祖宗不同才需要合并，否则已经合并了
    p[a] = b;
    Size[b] += Size[a];
}

(3)维护到祖宗节点距离的并查集：

int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

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

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

// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

原理介绍

参考1：算法训练营进阶篇。

参考2：秦淮岸dalao的讲义，https://www.acwing.com/blog/content/197/，举的例子非常棒！

参考3：https://zhuanlan.zhihu.com/p/93647900

参考4：https://oi-wiki.org/ds/dsu/

假设存在一个庞大的部落，人数众多，我们需要判断给出的两人是否具有亲戚关系。

现给定亲戚关系的两条重要性质：

1. 传递性：若x、y是亲戚，y、z是亲戚，那么x、z是亲戚；
2. 集合合并（连通集合）：若x、y是亲戚，则x的亲戚也是y的亲戚，y的亲戚也是x的亲戚。

我们可以用并查集来处理具有这两种性质的亲戚关系的判定问题。

算法步骤：1.初始化；2.查找；3.合并。

y总的模板真的很不错，hh。

还是直接上例题。

初始化时并查集编号从1开始！

洛谷P3367并查集（模板题）

题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式
第一行包含两个整数 N,M,表示共有 N 个元素和 M 个操作。

接下来 M 行，每行包含三个整数 Z,X,Y
当 Z=1 时，将 X与Y所在的集合合并。
当 Z=2 时，输出 X与Y是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式
对于每一个 Z=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

输入输出样例
输入
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
输出
N
Y
N
Y

对于 100% 的数据，1≤N≤10^4 ,1≤M≤2×10^5

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;

int p[N];// 存储每个点的祖宗结点
int n,m;

int find(int a){// 递归找到祖宗
    if (p[a] != a) p[a] = find(p[a]);
    return p[a];
}

int main(){
    scanf("%d%d",&n,&m);
    // 初始化编号
    for (int i = 1;i <= n;i++) p[i] = i;

    int z,x,y;char res;
    while (m--){
        scanf("%d%d%d",&z,&x,&y);
        if (z == 1) p[find(x)] = find(y);// 合并集合操作
        else{
            res = find(x) == find(y) ? 'Y' : 'N';
            printf("%c\n",res);
        }
    }
    return 0;
}

初始化：刚开始的时候每个点就是一个独立的集合,且这个集合树的树根就是本身。

查找：路径压缩，每次执行find操作的时候,把访问过的节点(也就是所有元素的父亲),都统统指向树根祖宗.这种方法可以避免出题人刻意卡掉链式结构。

N次合并M次查找的时间复杂度为：O(M*Alpha(N))，Alpha是Ackerman函数的某个反函数，在很大范围内它的值不超过4，接近线性，所以可以近似看成是：O(1)。

最坏情况时间复杂度为：O(m*logn)。这个记住就行。