数据结构：并查集 学习笔记
基础知识
并查集是一种树形数据结构。在全国青少年信息学奥林匹克系列竞赛大纲中难度为 6，是提高级中学习的数据结构。
并查集的基本操作：
- 查询一个元素在哪个集合。
- 合并两个集合。
使用一个森林来存储并查集，一个元素是一个结点，每棵树是一个集合。用一个数组 f 来记录父亲表示法。即 f[x] 表示元素节点 x 的父亲。这样，查询一个元素在哪个集合就是查询节点所在树的根节点，合并两个集合，就是把一颗树的根节点的父亲设置成另外一棵树的根节点。
并查集的优化
并查集有两种常用的优化操作，一种优化查询，一种优化合并。
查询：使用路径压缩，比较常用。容易发现，并查集只需要元素所在树的根节点，树的形态对操作没有影响。所以，可以在查询的时候，把所有查询的节点的父亲直接改成树根。（图来自《算法竞赛进阶指南》）
合并：使用启发式合并。把节点少的树合并到节点多的树上，一般只在边带权并查集中使用。这里不过多介绍，请读者自行查询相关资料。
并查集的代码实现
洛谷 P3367 【模板】并查集
题目链接
并查集模板，要注意初始化，即每个元素所在的集合最开始只有自身。
#include <iostream>
using namespace std;
// 1. 并查集的存储
int f[100005], n; // 并查集中有 n 个元素
// 2. 并查集的查询（带路径压缩优化）
int get(int x)
{
if (f[x] == x)
return x; // x 是根节点
return f[x] = get(f[x]); // 递归寻找根节点，并且进行路径压缩
}
// 3. 并查集的合并
void merge(int x, int y)
{
f[get(x)] = get(y);
}
int main()
{
int m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
f[i] = i; // 4. 并查集的初始化
while (m--) {
int x, y, z;
cin >> z >> x >> y;
if (z == 1)
merge(x, y);
else {
if (get(x) == get(y))
cout << 'Y' << endl;
else
cout << 'N' << endl;
}
}
return 0;
}
统计并查集集合个数
在一些题中，需要我们统计并查集中集合个数。统计有多少树的根节点即可（根节点的父节点是他本身）
我们来看下面这题：
洛谷 P1536 村村通
题目描述：
某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？
输入格式：
输入包含若干组测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目 n 和道路数目 m ；随后的 m 行对应 m 条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从 1 到 n 编号。注意：两个城市间可以有多条道路相通。在输入数据的最后，为一行一个整数 0，代表测试数据的结尾。
输出格式：
对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。
做法：
初始时，我们用并查集把所有直接连通的城镇合并。统计出集合数，显然集合数减一就是最少要建设的道路。
参考代码：
#include <iostream>
using namespace std;
int f[1005], n, m;
int get(int x)
{
// 1. 并查集的查询，这里我用三元表达式压了下行
return (f[x] == x) ? (x) : (f[x] = get(f[x]));
}
int main()
{
ios::sync_with_stdio(0);
do {
cin >> n;
if (n == 0)
break;
cin >> m;
for (int i = 1; i <= n; i++)
f[i] = i;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
f[get(x)] = get(y); // 2. 并查集的合并
}
int ans = 0;
for (int i = 1; i <= n; i++)
ans += (i == get(i)); // 3. 统计集合个数（就是统计根节点个数）
cout << ans - 1 << endl;
} while (n != 0);
return 0;
}
带权并查集
有时候，我们除了需要并查集的两个基本操作外，还需要维护节点或者集合的一些其他信息。当我们维护集合的信息时，可以把信息记在集合的根节点上。当我们维护节点的信息是节点到根节点的距离或者其他与根节点相关的信息时，就使用边带权并查集，把信息记在节点到父节点的边上，在路径压缩时处理。
洛谷 P1196 [NOI2002] 银河英雄传说
（未完待续）
标签：get,int,查集,笔记,查询,集合,数据结构,节点 From： https://www.cnblogs.com/JXOIer-zaochen/p/16997939.html