From 8c3ec9a5a8eb1758799bf8741f555b6abdb90da7 Mon Sep 17 00:00:00 2001
From: symkube <43703966+symkube@users.noreply.github.com>
Date: Sat, 16 Mar 2019 10:21:54 +0800
Subject: [PATCH] Update dsu.md
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

详细叙述了“启发式合并”的部分，增加了“带权并查集”
---
 docs/ds/dsu.md | 19 +++++++++++++++++--
 1 file changed, 17 insertions(+), 2 deletions(-)

diff --git a/docs/ds/dsu.md b/docs/ds/dsu.md
index 584cedda..6a57d16b 100644
--- a/docs/ds/dsu.md
+++ b/docs/ds/dsu.md
@@ -1,10 +1,12 @@
-并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的 **合并** 及 **查询** 问题。  
+并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的 **合并** 及 **查询** 问题。
 它支持两种操作：
 
 -   查找（Find）：确定某个元素处于哪个子集；
 
 -   合并（Union）：将两个子集合并成一个集合。
 
+*也就是说，不支持集合的分离、删除。  
+
 ## 初始化
 
 ```cpp
@@ -69,7 +71,13 @@ void unionSet(int x, int y)  // x与y所在家族合并
 
 一个祖先突然抖了个机灵：「你们家族人比较少，搬家到我们家族里比较方便，我们要是搬过去的话太费事了。」
 
-启发式合并是将深度小的集合合并到深度大的集合（也称为 **按秩合并** ），但是笔者认为路径压缩之后它就失去意义了，或者不如按照节点数量合并，这样还可以减少下次路径压缩的工作量。（反正启发式合并用得很少，路径压缩已经够快了。）
+由于我们维护的只是集合的合并、查询操作，当我们需要将两个集合合二为一时，无论将哪一个集合连接到另一个集合的下面，都能得到正确的结果。但不同的连接方法存在时间复杂度的差异。具体来说，如果我们将一个点数与深度都较小的集合树连接到一个更大的集合树下，显然会比相反的连接方案带来更好的期望复杂度（也会带来更优的最坏复杂度）。
+
+当然，我们不总能遇到恰好如上所述的集合————点数与深度都更小。鉴于点数与深度这两个并查集中的特征都很容易维护，我们常常从中择一，作为启发函数。而无论选择哪一个，都能带来正确的复杂度，也就是$\Theta (m\alpha(m,n))$，具体的证明。
+
+在算法竞赛的实际代码中，即便不使用启发式合并，代码也往往能够在规定时间内完成任务。在Tarjan的论文[1]中，证明了不使用启发式合并、只使用路径压缩会带来$\Theta (m lg n)$的最坏复杂度。在姚期智的论文[2]中，证明了不使用启发式合并、只使用路径压缩，在平均情况下，依然是$\Theta (m\alpha(m,n))$。
+
+下述代码示例基于深度进行合并。
 
 ```cpp
 int size[N];  //记录子树的大小
@@ -93,6 +101,9 @@ void unionSet(int x, int y) {
 
 显然为 $O(n)$ 。
 
+## 带权并查集
+我们还可以在并查集的边上定义某种权值、以及这种权值在路径压缩时产生的运算，从而解决更多的问题。比如对于经典的《食物链》（NOI2001），我们可以在边权上维护模3加法群。
+
 ## 经典题目
 
 [\[NOI2015\]程序自动分析](https://www.lydsy.com/JudgeOnline/problem.php?id=4195)
@@ -106,3 +117,7 @@ void unionSet(int x, int y) {
 ## 其他应用
 
 [最小生成树](/graph/mst)Kruskal 是基于并查集的算法。
+
+[1]Tarjan, R. E., & Van Leeuwen, J. (1984). Worst-case analysis of set union algorithms. Journal of the ACM (JACM), 31(2), 245-281.
+[2]Yao, A. C. (1985). On the expected performance of path compression algorithms. SIAM Journal on Computing, 14(1), 129-133.
+[3]上面两个论文引用源自https://www.zhihu.com/question/28410263/answer/40966441
-- 
2.11.0