From 367cd72e6cbd26b25dcae59a4010cd60d439d63b Mon Sep 17 00:00:00 2001
From: Trisolaris HD <36555123+TrisolarisHD@users.noreply.github.com>
Date: Wed, 27 Mar 2019 17:13:58 +0800
Subject: [PATCH] Update dsu.md

---
 docs/ds/dsu.md | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

diff --git a/docs/ds/dsu.md b/docs/ds/dsu.md
index 04f5c6f6..29024147 100644
--- a/docs/ds/dsu.md
+++ b/docs/ds/dsu.md
@@ -22,7 +22,8 @@ void makeSet(int size) {
 !!! 举个例子  
 几个家族进行宴会，但是家族普遍长寿，所以人数众多。由于长时间的分离以及年龄的增长，这些人逐渐忘掉了自己的亲人，只记得自己的爸爸是谁了，而最长者（称为「祖先」）的父亲已经去世，他只知道自己是祖先。为了确定自己是哪个家族，他们想出了一个办法，只要问自己的爸爸是不是祖先，一层一层的向上问，直到问到祖先。如果要判断两人是否在同一家族，只要看两人的祖先是不是同一人就可以了。
 
-在这样的思想下，并查集的查找算法诞生了。我们可以用代码模拟这个过程。
+在这样的思想下，并查集的查找算法诞生了。
+此处给出一种 C++ 的参考实现：
 
 ```cpp
 int fa[MAXN];  //记录某个人的爸爸是谁，特别规定，祖先的爸爸是他自己
@@ -39,8 +40,8 @@ int find(int x) {
 
 ### 路径压缩
 
-这样的确可以达成目的，但是显然效率实在太低。为什么呢？因为我们使用了太多没用的信息，我关心的是我祖先是谁，我爸爸是谁没什么关系，这样一层一层找太浪费时间，不如我直接当祖先的儿子，问一次就可以出结果了。甚至祖先是谁都无所谓，只要这个人可以代表我们家族就能得到想要的效果。 **把在路径上的每个节点都直接连接到根上** ，这就是路径压缩。
-于是用代码实现它。
+这样的确可以达成目的，但是显然效率实在太低。为什么呢？因为我们使用了太多没用的信息，我的祖先是谁与我父亲是谁没什么关系，这样一层一层找太浪费时间，不如我直接当祖先的儿子，问一次就可以出结果了。甚至祖先是谁都无所谓，只要这个人可以代表我们家族就能得到想要的效果。 **把在路径上的每个节点都直接连接到根上** ，这就是路径压缩。
+此处给出一种 C++ 的参考实现：
 
 ```cpp
 int find(int x) {
@@ -54,6 +55,7 @@ int find(int x) {
 
 宴会上，一个家族的祖先突然对另一个家族说：我们两个家族交情这么好，不如合成一家好了。另一个家族也欣然接受了。  
 我们之前说过，并不在意祖先究竟是谁，所以只要其中一个祖先变成另一个祖先的儿子就可以了。
+此处给出一种 C++ 的参考实现：
 
 ```cpp
 void unionSet(int x, int y) {
@@ -70,13 +72,13 @@ void unionSet(int x, int y) {
 
 一个祖先突然抖了个机灵：「你们家族人比较少，搬家到我们家族里比较方便，我们要是搬过去的话太费事了。」
 
-由于需要我们支持的只有集合的合并、查询操作，当我们需要将两个集合合二为一时，无论将哪一个集合连接到另一个集合的下面，都能得到正确的结果。但不同的连接方法存在时间复杂度的差异。具体来说，如果我们将一个点数与深度都较小的集合树连接到一个更大的集合树下，显然会比相反的连接方案带来更好的期望复杂度（也会带来更优的最坏复杂度）。
+由于需要我们支持的只有集合的合并、查询操作，当我们需要将两个集合合二为一时，无论将哪一个集合连接到另一个集合的下面，都能得到正确的结果。但不同的连接方法存在时间复杂度的差异。具体来说，如果我们将一棵点数与深度都较小的集合树连接到一棵更大的集合树下，显然相比于另一种连接方案，其期望复杂度更优（也会带来更优的最坏复杂度）。
 
-当然，我们不总能遇到恰好如上所述的集合————点数与深度都更小。鉴于点数与深度这两个特征都很容易维护，我们常常从中择一，作为启发函数。而无论选择哪一个，复杂度都是正确的，也就是 $\Theta (m\alpha(m,n))$，具体的证明。
+当然，我们不总能遇到恰好如上所述的集合————点数与深度都更小。鉴于点数与深度这两个特征都很容易维护，我们常常从中择一，作为估价函数。而无论选择哪一个，时间复杂度都为 $\Theta (m\alpha(m,n))$，具体的证明可参见 References 中引用的论文。
 
 在算法竞赛的实际代码中，即便不使用启发式合并，代码也往往能够在规定时间内完成任务。在 Tarjan 的论文[1]中，证明了不使用启发式合并、只使用路径压缩的最坏时间复杂度是 $\Theta (m \log n)$。在姚期智的论文[2]中，证明了不使用启发式合并、只使用路径压缩，在平均情况下，时间复杂度依然是 $\Theta (m\alpha(m,n))$。
 
-下述代码示例基于深度进行合并。
+此处给出一种 C++ 的参考实现，其选择深度作为估价函数：
 
 ```cpp
 int size[N];  //记录子树的大小
@@ -101,6 +103,7 @@ void unionSet(int x, int y) {
 显然为 $O(n)$ 。
 
 ## 带权并查集
+
 我们还可以在并查集的边上定义某种权值、以及这种权值在路径压缩时产生的运算，从而解决更多的问题。比如对于经典的「NOI2011」食物链，我们可以在边权上维护模 3 意义下的加法群。
 
 ## 经典题目
@@ -117,6 +120,8 @@ void unionSet(int x, int y) {
 
 [最小生成树算法](/graph/mst)中的 Kruskal 是基于并查集的算法。
 
+## References
+
 - [1]Tarjan, R. E., & Van Leeuwen, J. (1984). Worst-case analysis of set union algorithms. Journal of the ACM (JACM), 31(2), 245-281.    [ResearchGate PDF](https://www.researchgate.net/profile/Jan_Van_Leeuwen2/publication/220430653_Worst-case_Analysis_of_Set_Union_Algorithms/links/0a85e53cd28bfdf5eb000000/Worst-case-Analysis-of-Set-Union-Algorithms.pdf)
 - [2]Yao, A. C. (1985). On the expected performance of path compression algorithms. [SIAM Journal on Computing, 14(1), 129-133.](https://epubs.siam.org/doi/abs/10.1137/0214010?journalCode=smjcat)     
-- [3]上面两个论文引用源自[知乎回答：是否在并查集中真的有二分路径压缩优化？](https://www.zhihu.com/question/28410263/answer/40966441)     
+- [3][知乎回答：是否在并查集中真的有二分路径压缩优化？](https://www.zhihu.com/question/28410263/answer/40966441)     
-- 
2.11.0