目录
- 并查集
- 并查集
- 并查集是什么
- 初始化
- 查询
- 路径压缩
- 合并
- 特别的
- 还有...
- 模板
- 复杂度
- Ex-并查集
- 带删除并查集
- Why?
- 例?
- Why普通并查集删除会出Bug
- 带删除并查集
- 例题
- Luogu P2024「NOI2011」食物链
- 参考
- 并查集
并查集
并查集
并查集是什么
并查集(Union-Find)是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素．
顾名思义，并查集支持两种操作：
- 合并（Unite）：合并两个元素所属集合（合并对应的树）．
- 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合．
看不懂？
本质就是记录每一个元素的father
从而实现一些特殊的处理。
甜菜😋😋
初始化
init()
初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树．方便起见，我们将根节点的父亲设为自己
代码 懒得C了
查询
我们需要沿着树向上移动，直至找到根节点．
1
↑ ↖
2 3↑ ↖4 5
（1， 3， 4）
上升。
size_t dsu::find(size_t x) { return pa[x] == x ? x : find(pa[x]); }
路径压缩
查询过程中经过的每个元素都属于该集合，我们可以将其直接连到根节点以加快后续查询．
1
↑ ↖
2 3↑ ↖4 5
可以压缩成
1
↑ ↖ ↖ ↖
2 3 4 5
查询速度++
size_t dsu::find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
合并
要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点．
（图懒的画.jpeg）
void dsu::unite(size_t x, size_t y) { pa[find(x)] = find(y); }
特别的
- 并查集中的「集」指的是不相交的集合，即元素互不重复、互不重叠的若干集合。
- 并查集中的「并」指的是集合的并集操作，即将两个不同的集合合并为一个更大的集合。
比如：
{1, 3, 5, 7} U {2, 4, 6, 8} = {1, 2, 3, 4, 5, 6, 7, 8}
还有...
并查集的两种思路：
- 查询牛逼的：使用一个数组来表示每个元素所属的集合
- 合并牛逼的，就是我们之前讲的，但查询也可以用合并来弥补
所以，优先选择2. 👍👍
模板
现在就可以写代码了！！！
struct dsu {vector<size_t> pa;explicit dsu(size_t size) : pa(size) { iota(pa.begin(), pa.end(), 0); }size_t dsu::find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }void dsu::unite(size_t x, size_t y) { pa[find(x)] = find(y); }
};
复杂度
大约在\(O(h)\) \(h\)为深度
压缩之后为\(O(1)\)（单次查询）
Ex-并查集
带删除并查集
我们使用虚点法，它的核心思想是：
为每个实际数据节点创建一个虚点：在初始化时，每个实际的数据节点（比如x）都有一个对应的虚点（比如x'）。虚点作为数据节点的父节点。
- 为每个实际数据节点创建一个虚点：在初始化时，每个实际的数据节点（比如x）都有一个对应的虚点（比如x'）。虚点作为数据节点的父节点。
- 初始时，x的父节点是x'，而x'的父节点是它自己（即x'是根）。
- 合并操作：当需要合并两个集合时，总是合并它们的虚点（即虚点的根）。这样，实际的数据节点始终是叶子节点，只有虚点会有子节点。
- 删除操作：要删除一个数据节点（比如x），只需将x的父指针指向一个新的虚点（比如x''），这样x就从原来的集合中脱离出来。由于x原本是叶子节点，删除它不会影响其他节点。
Why?
- 数据节点始终是叶子：因为所有的合并操作都是在虚点之间进行的，数据节点永远不会成为其他节点的父节点。因此，删除一个数据节点时，不会影响其他节点的连接关系。
- 删除操作：删除x时，只需将x重新指向一个新的虚点（即一个新的集合）。原来的虚点和其他节点的结构保持不变。
例?
假设有三个数据节点：A, B, C。初始化时：
- A -> A'（A'的父是A'）
- B -> B'（B'的父是B'）
- C -> C'（C'的父是C'）
现在合并A和B：
- 找到A的虚点A'和B的虚点B'，将A'的父设为B'（或反之）。
- 假设A' -> B'，B' -> B'
- 现在：A -> A' -> B'，B -> B' -> B'，C -> C' -> C'
此时，A和B属于同一个集合（根为B'），C属于另一个集合（根为C'）。
Why普通并查集删除会出Bug
假设不使用虚点法，直接合并A和B：
- A -> B, B -> B
- 现在删除A：
- 如果直接断开A -> B，那么A成为一个独立的点，但B的结构不变。
- 但如果A有子节点（比如C -> A），删除A会导致C失去父节点。
虚点法避免了这个问题，因为数据节点（如A, B, C）始终是叶子，没有子节点。
例题
Luogu P2024「NOI2011」食物链
将一种生物 \(x\) 拆分为三种状态．在具体实现中，我们可以直接将不同的状态当作不同的元素：
- 与 \(x\) 处于同一集合的状态与 \(x\) 属于同一物种；
- 与 \(x + n\) 处于同一集合的状态能被 \(x\) 吃；
- 与 \(x+2n\) 处于同一集合的能吃 \(x\)．
于是，对于一句话：
1 x y为假话当且仅当：- \(x>N\)或 \(y>N\)；
- \(y\) 与 \(x+n\) 或 $x+2n 中的一个处于同一集合内．
2 x y为假话当且仅当：- \(x>N\) 或 \(y>N\)；
- \(y\) 与 \(x\) 或 \(x+2n\) 中的一个处于同一集合内．
- 若为真话，合并对应状态．
Code:
int n, m;
cin >> n >> m;
DSU dsu(n * 3 + 1);
int res = 0;
for (; m; --m)
{int op, x, y;cin >> op >> x >> y;if (x > n || y > n)++res;else if (op == 1){if (dsu.find(x) == dsu.find(y + n) ||dsu.find(x) == dsu.find(y + (n << 1))){++res;}else{dsu.unite(x, y);dsu.unite(x + n, y + n);dsu.unite(x + n * 2, y + n * 2);}}else{if (dsu.find(x) == dsu.find(y) || dsu.find(x) == dsu.find(y + n)){++res;}else{dsu.unite(x, y + n * 2);dsu.unite(x + n, y);dsu.unite(x + n * 2, y + n);}}
}
cout << res << endl;
参考
- 并查集 - OI Wiki
- 5.8 并查集 | 算法通关手册（LeetCode）
- 并查集_百度百科
- 并查集及其应用专题--全网最详细版 - hicode002 - 博客园