acm 并查集.pdf

并查集是若干个不相交集合,能够 实现较快的合并和判断元素所在集合的操作。一般采取树形结构来存 储并查集,并利用一个rank 数组来存储集合的深度下界,在查找操 作时进行路径压缩使后续的查找操作加速。可以看成是将编号分别为 1...N 的N 个对象划分为不相交集合,在每个集合中,选择其中某个 元素代表所在集合。