并查集学习笔记

简介

这里引用OI-wiki上的内容：

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。
顾名思义，并查集支持两种操作：
合并（Union）：合并两个元素所属集合（合并对应的树）
查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

看不懂？

简单来说，并查集就是一种简单的判断两个元素是否在同一个集合中，或者说，有相同的“祖先”。并查集支持查讯，合并等操作。

并查集的基本逻辑可以做个类比：拜师！假设有两个习武之人要比拼比拼，可能在现实生活中他们会打一打，但是在并查集的逻辑中，他们是叫他们的师傅（也就是术语中的“祖先”）来比拼一番。输了的那一方将会带着这一派整个加入到另一个老师傅的帮派中。

示范代码

并查集模板题

首先，我们要有一个用来记录每个元素祖先的数组fa，在一开始，每个元素的祖先就是它本身，于是我们可以写出代码：

void init(){ // 本人习惯用函数来初始化
    for (int i = 1; i <= n; i++) fa[i] = i;
    return ;
}

但是题目的要求不止这些，我们先来实现查询每个元素的祖先。我们可以知道，如果一个元素没有被合并，那么它的祖先一定是自己。那么我们可以不断查找某个元素的直接祖先是谁，再查找那个元素的祖先，直到那个元素的祖先是它本身为止。

同时为了优化，我们可以在查找的过程中将中途所经历的元素的祖先直接设为最后的祖先，也就是修为高深的老师傅。因为总体来说这些元素仍处于最终的祖先的管理之下，所以不会导致混乱：

int find(int x){
    if (fa[x] == x) return x; // 找到了祖先
    return fa[x] = find(fa[x]);
}

或者用三元运算符的形式：

1
2
3

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

并查集的合并操作，说难也不难，就是修改每个元素在fa数组里的值即可，那么我们可以写出以下代码：

void merge(int x, int y){
    int fx = find(x), fy = find(y); // 查找两个元素的祖先
    if (fx == fy) return ; // 在同一个集合中就跳过
    fa[fx] = fy;
    return ;
}

那么最终可以写出代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, fa[10005];

void init(){
    for (int i = 1; i <= n; i++) fa[i] = i;
    return ;
}

int find(int x){
    if (fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}

void merge(int x, int y){
    int fx = find(x), fy = find(y);
    if (fx == fy) return ;
    fa[fx] = fy;
    return ;
}

int main(){
    cin >> n >> m;
    init();
    int z, x, y;
    for (int i = 0; i < m; i++){
        cin >> z >> x >> y;
        if (z == 1) merge(x, y);
        else{
            if (find(x) == find(y)) cout << "Y" << endl;
            else cout << "N" << endl;
        }
    }
    return 0;
}

练习题：

带权并查集

我们可以在并查集的边上定义某种权值（比如大小，长度等）来解决更多的问题。

来看P1196 [NOI2002] 银河英雄传说这道题。在这道题中，我们要实现合并和查询两种操作。我们可以想到维护每个舰队的长度，但为了更精确的描述两艘战舰之间的距离，我们还要维护每艘战舰到队列头部的距离。所以我们不难写出以下代码：

#include <bits/stdc++.h>
using namespace std;

int t, fa[30005], a, b, l[30005], front[30005];
char op;

int find(int x){
	if (fa[x] == x) return x;
	int k = fa[x]; // 要先保存下来父节点
	fa[x] = find(fa[x]);
	front[x] += front[k]; // 更新当前战舰到队列头部的距离
	l[x] = l[fa[x]]; // 更新队列长度
	return fa[x];
}

int main(){
	cin >> t;
	for (int i = 1; i <= 30000; i++){
		fa[i] = i;
		l[i] = 1;
		front[i] = 0;
	}
	while(t--){
		cin >> op >> a >> b;
		if (op == 'M'){
			int x = find(a), y = find(b);
			if (x == y) continue;
			fa[x] = y; // 进行合并操作
			front[x] += l[y]; // 修改原来队列头部的战舰到新的队列头部的距离
			l[x] += l[y]; // 更新队列长度
			l[y] = l[x];
		}
		else{
			int x = find(a), y = find(b);
			if (x != y) cout << -1 << endl;
			else cout << abs(front[a] - front[b]) - 1<< endl;
		}
	}
	return 0;
}

练习题：

种类并查集

种类并查集适用于拥有对称关系的题目，比如敌人的敌人是朋友之类的。解决这种问题，我们一般会把这种关系所指代的对象建立一个虚拟的节点，然后再把满足这个关系的节点与这个虚拟节点进行合并。

比如P1892 [BOI2003] 团伙这道题，我们可以对每个人的敌人建立一个虚拟节点，然后将具有敌对关系的人与虚拟节点进行合并即可。不难写出这样的代码：

#include <bits/stdc++.h>
using namespace std;

int n, fa[2010], m, p, q;
char opt;

void init(){
	for (int i = 1; i <= n * 2; i++) fa[i] = i; // 注意初始化节点的规模要扩大一倍
	return ;
}

int find(int x){
	if (x == fa[x]) return fa[x];
	return fa[x] = find(fa[x]);
}

void merge(int x, int y){
	if (find(x) == find(y)) return ;
	fa[find(x)] = find(y);
	return ;
}

int main(){
	cin >> n >> m;
	init();
	for (int i = 1; i <= m; i++){
		cin >> opt >> p >> q;
		if (opt == 'F'){
			merge(p, q);
		}
		else{// 节点i的敌人为i + n
			merge(q + n, p);
			merge(p + n, q);
		}
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) if (fa[i] == i) cnt++;
	cout << cnt;
	return 0;
}

练习题：