ACM资料
cyfhz10.27KB需要积分:1资源文件列表:
并查集.zip 大约有1个文件 
并查集.ppt 44.5KB
资源介绍:
ACM 地方都是法师东方时代
并查集
Yali 朱全民
分离集合
在有的问题中，需要对不相交的集合 (disjoint
set) 进行这样两种操作：
–
检索某元素属于哪个集合
–
合并两个集合
能够维护这两个操作的数据结构，我们称之为
并查集。
并查集的森林实现
一般来说我们用森林的结构实现并查集
在森林中，每棵树代表一个集合。用树根来表
示这个集合。
合并操作：两个集合 S1 、 S2 合并，将其中
的一个树根作为另一个树根的子树即可。
查找操作：对于一个元素 u 的查找，顺着 u 往
上找，直到线索到根节点，也就确定了 u 所在
的集合。
两个优化
启发式合并：
在合并集合 S1 、 S2 的时候，我们让较
小的树成为较大的树的子树。这里可以是深度、
节点个数等启发函数来比较树的大小。
路径压缩：
我们在查找完 u 至根节点的路径之后，
一般将这条路径上的所有节点的父节点都设为
根节点，这样可以大大减少之后的查找次数。
并查集的时间复杂度
可以证明，经过启发式合并和路径压缩之后的
并查集，执行 m 次查找的复杂度为 O(mα(m))
其中 α(m) 是 Ackermann 函数的某个反函数，
你可以近似的认为它是小于 5 的。所以并查集
的单次查找操作的时间复杂度也几乎是常数级
的。
android_wxg
lonewolf010
wanghuannihao1992
blastonly
qq_45704942
u012319493
pandengyisun
qq_51400272