分离集合
• 在有的问题中，需要对不相交的集合(disjoint set)进行这样两种操
作：
• 检索某元素属于哪个集合
• 合并两个集合
• 此时，我们可以使用并查集维护这两个操作。
并查集的森林实现
• 一般来说我们用森林的结构实现并查集
• 在森林中，每棵树代表一个集合。
• 对每个元素，记录它在森林中的父亲f[i]
• 对于根节点而言有f[i]=i，表示它是这个集合的代表元。
• 合并操作：两个集合S1、 S2合并，将其中的一个树根作为另一
个树根的子树即可。
• 查找操作：对于一个元素u的查找，顺着u往上找，直到线索到
根节点，也就确定了u所在的集合。
两个优化
• 启发式合并：
在合并集合S1、 S2的时候，我们让较小的树成为较大的树的
子树。这里可以是深度、节点个数等启发函数来比较树的大小。
• 路径压缩：
我们在查找完u至根节点的路径之后，一般将这条路径上的
所有节点的父节点都设为根节点，这样可以大大减少之后的查找
次数。
并查集的时间复杂度
• 可以证明，经过启发式合并和路径压缩之后的并查集，执行m次
查找的复杂度为O(mα(m))
• 其中α(m)是Asizekermann函数的某个反函数，你可以近似的认为
它是小于5的。所以并查集的单次查找操作的时间复杂度也几乎
是常数级的。
EG:
银河英雄传说(NOI2002)
可爱的猴子(POI2003)
带边权无向图最小连通代价
• 给出一个每条边带有权值的无向图。
• 我们可以删除图里面的一些边，从而使得图当中最大的边的边权
尽量小，但是我们需要保证点1和点N仍然是连通的。
带边权无向图最小连通代价
• 对于“最小的最大”或者“最大的最小”这一类字眼，我们经常会用
到二分答案的方法。
• 对于这一题，我们可以尝试二分最大边权的最小值，然后我们只
加入比这个值小的边，然后通过BFS（或DFS）去检查点1和点N是
不是连通的。
EG：
noip2013 货车运输
如果你不开心，那我就把右边
这个帅傻子分享给你吧，
你看，他这么好看，跟个zz一样看着你，你还伤心吗？
真的！这照片盯上他五秒钟就想笑了。
一切都会过去的。
时间时间会给你答案2333