并查集

BraumAce2024年7月27日约 1589 字大约 5 分钟

并查集

简介

1.并查集是一种非常精巧实用的数据结构，它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图，求最小生成树的 Kruskal 算法和求最近公共祖先（LCA）等。

2.基本操作主要有：

（1）初始化 init
（2）查询 find
（3）合并 union

基本模板

1.初始化

int fa[N];
void init(int n){
    for (int i = 1; i <= n; i++)
        fa[i] = i;  // 一开始都是独立的，父节点设置为自己
}

假如有编号为 1，2，3，...，n 的 n 个元素，我们用一个数组 fa[N] 来存储每个元素的父节点。一开始，我们先将它们的父节点设为自己。

2.查询（已路径压缩）

查询一定要进行路径压缩，不然大概率会超时。

int find(int x){
    //递归出口，当达到了祖先位置，就返回祖先
    if (fa[x] == x)
        return x;
    else {
        //不断往上查找祖先，并进行路径压缩，一直找到祖先的祖先
        fa[x] = find(fa[x]);
        
        return fa[x]; //返回父亲节点
    }
}

也可以简写成这样：

int fond(int x){
	return fa[x] == x ? x : find(fa[x]);
}

3.合并

最简单的合并就是像下面这样，粗暴的把 i 所在树的根节点接到 j 所在树的根节点下面，但是有可能出现 “头重脚轻” 的不平衡状况，后面例二中将会给出解决方法。

void union(int i, int j){
    int x = find(i); // 找到i的根节点
    int y = find(j); // 找到j的根节点
    fa[x] = y;       // i的根节点指向j的根节点
}

典例分析

例一：亲戚关系

现在有若干家族图谱关系，给出了一些亲戚关系，如 A 和 B 是亲戚，B 和 C 是亲戚，那么 A和 B 也是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。

【输入格式】

第一部分是以 N，M 开始。N 为人数（ $1 \leqslant N \leqslant 20000$ ），这些人的编号为 1，2，3，...，N。
下面有 M行（ $1 \leqslant M \leqslant 1000000$ ），每行有两个数 a，b，表示 a 和 b 是亲戚。

第二部分是以 Q 开始。以下 Q 行有 Q 行询问（ $1 \leqslant Q \leqslant 1000000$ ），每行为 c, d, 表示询问 c 和 d 是否为亲戚。

【输出格式】

对于询问 c, d, 输出一行：若 c, d 为亲戚，则输出 “YES” ，否则输出 “NO”。

【输入样例】

【输出样例】

YES
NO
YES

【示例代码】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int N = 20005;

int fa[N];  // 父亲数组

// 初始化父亲为它自己
void init (int n){
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}

// 查找根节点
int find(int x){
    if (fa[x] == x)
        return x;
    else {
        // 压缩路径，不断向上寻找最初的根节点
        fa[x] = find(fa[x]);
        return fa[x];
    }
}

// 合并，子节点依附在根节点上
void union(int i, int j){
    int x= find(i);
    int y = find(j);
    fa[x] = y;
}

int main(){
    int n, m, x, y, q;
    cin >> n >> m;
    
    init(n);
    for (int i = 1; i <= m; i++){
        cin >> x >> y;
        union(x, y);  // 构建依附关系
    }
    
    scanf("%d", &q);
    for (int i = 1; i <= q; i++){
        cin >> x >> y;
        // 询问是否存在依附关系
        if (find(x) == find(y)) put("YES");
        else put("NO");
    }
    
    return 0;
}

例二：洛谷 P3367 【模板】并查集

find 的主要功能就是从某个节点向上遍历到根节点，其时间复杂度就是树的高度，我们可能习惯性地认为树的高度就是 logN ，但是不一定。logN 的高度只存在于平衡二叉树，对于一般的树可能出现极端不平衡的情况，使得 “树” 几乎退化成 “链表'，树的高度最坏情况下可能变成 N。

问题的关键在于，该如何想办法避免树的不平衡呢？

其实关键在于 union 过程。

我们其实是希望，高度小一些的树接到大一些的树下面，这样就能避免头重脚轻，更平衡一些。

解决方法是额外使用一个 size 数组，记录每棵树包含的节点数，不妨称为高度。

如下所示：

void union(int i, int j){
	int x = find(i), y = find(j);
	
	if (x == y) return;
		
	// 小树接在大树下面，较平衡
	if (size[x] >= size[y]){
        fa[y] = x;
        size[x] += size[y];
    }
    else {
        fa[x] = y;
        size[y] += size[x];
    }
    return;
}

下面看题中完整的写法（题是比较简单的一道模板题，用这种写法不过是略微优化了一下）:

【题目描述】

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

【输入格式】

第一行包含两个整数 N, M, 表示共有 N 个元素和 M 个操作。
接下来 M 行，每行包含三个整数 $Z_i, X_i, Y_i$ 。
当 $Z_i = 1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。
当 $Z_i = 2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出 Y；否则输出 N。

【输出格式】

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

【输入样例】

【输出样例】

N
Y
N
Y

【示例代码】

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 2e5+5;

// 父亲数组，高度数组
int fa[N], size[N];

// 初始化
int init(int n)
{
    for (int i = 1; i <= n; i++){
        fa[i] = i;    // 初始根节点为它自己
        size[i] = 1;  // 初始高度为1
    }
}

// 查找父节点
int find(int x)
{
    if (fa[x] == x)
        return x;
    else
        fa[x] = find(fa[x]);  // 扁平化处理，压缩路径
    return fa[x];
}

// 合并
void union(int i, int j)
{
    int x = find(i), y = find(j);

    if (x == y) return;
	
    // 比较高度，高度小的接在高的下面，节省查找时间
    if (size[x] >= size[y]){
        fa[y] = x;
        size[x] += size[y];
    }
    else {
        fa[x] = y;
        size[y] += size[x];
    }
}

int main()
{
    int n, m, z, x, y;
    cin >> n >> m;

    init(n);//初始化

    for (int i = 1; i <= m; i++){
        cin >> z >> x >> y;

        if (z == 1) union(x, y);

        if (z == 2){
            if (find(x) == find(y))
                cout << "Y" << endl;
            else
                cout << "N" << endl;
        }
    }

    return 0;
}