并查集的全名是Disjoint Set Union。
1
并查集就是解决若干元素所属的集合关系的一类问题
简单来说并查集一般有以下几个操作:将两个元素所在的集合合并;查找某个元素所在的集合(根节点)
2
初始化
一般的,在初始情况下,每个元素自成一个集合,这个集合的根节点就是元素本身。
用数组fa[]来记录该并查集的话,初始化应该是这样的:
1 | void init(int x) { //并查集元素个数 |
查找根节点
简单的,不断顺着数组fa[]“逆流而上”查找,直到fa[x] = x时就找到根节点了,可以用递归或者循环实现。
1 | int get(int x) { // 获取x的根节点 |
注意,并查集有可能遇到这样的糟糕情况:
当我们试图查找节点5的根节点时,我们需要遍历整个并查集才能找到节点1。在百万或以上的数据规模中,这种无意义的时间消耗是致命的,所以我们需要路径压缩,将上图的情况优化成这样:
这样从节点5就可以一次性找到节点1了。
代码优化后实现如下
1 | int get(int x) { // 获取x的根节点 |
合并
将两个并查集合并,只要统一它们的父亲节点即可。当两个并查集拥有同一个根节点的时候,意味着它们是一个并查集。
举例,如图,合并并查集{1,2,3}和并查集{4,5}只需要将{1,2,3}的根节点置为4或将{4,5}的根节点置为1
像这样:
代码实现如下
1 | void merge(int x, int y) { //将元素x和元素y所在的集合合并 |
3 例题
以洛谷P3367为例
题目描述
如题,现在有一个并查集,你需要完成合并和查询操作。
输入输出格式
输入格式:
1 | 第一行包含两个整数N、M,表示共有N个元素和M个操作。 |
输出格式:
1 | 如上,对于每一个Zi=2的操作,都有一行输出,每行包含一个大写字母,为Y或者N |
输入输出样例
输入样例#1:
1 | 4 7 |
输出样例#1:
1 | N |
说明
时空限制:1000ms,128M
数据规模:
对于30%的数据,N<=10,M<=20;
对于70%的数据,N<=100,M<=1000;
对于100%的数据,N<=10000,M<=200000。
AC代码
1 |
|