并查集的初级应用及进阶 并查集的初级应用及进阶 一、精华 精华提炼 1： 内容：并查集就是树的孩子表示法的应用。 解释：对于下图所示树，它的孩子表示法为： belg[5]=2, belg[6]=2, belg[7]=2; belg[2]=1, belg[3]=1, belg[4]=1; belg[1]=1(也可以=-1,只要能够识别它是根就可以) 精华提炼 2： 内容：并查集的孩子父亲表示法中，每个节点与其父亲节点可以添加一个关系属性(必须具有可传递性)。 解释：比如，节点表示一个人，关系属性为一个人的性别。我们先用上图来解释这个关系属性的应用，在后文具体展开。我们可以这样定义，如果节点 i 和其父节点 j 性别相同（belg[i]=j），则 kind[i]=false, 反之，kind[i]=tru e，那么如果我们知道kind[5]=tru e，kind[2]=false，那么5 和2 的父节点1的关系为kind[5]^kind[2]=tru e，即他们性别不同。 二、基础 基础 1：集合表示 根据精华提炼 1，我们把一颗树的节点集合看成以根节点命名的集合，那么上面的集合我们可以认为是集合 1。 下图共有两个集合，分别为集合 1，集合 2。 基础 2：元素关系 如何判断元素关系呢？其实，我们只需找出元素对应的集合名称，然后判断名称是否相同即可。寻找集合名称代码如下： int Find(int x) { while ( belg[x]!=x ) x = belg[x]; return x; } 例如：对于基础1 中左图,有belg[5]=2，belg[2]=2。那么5 属于集合2。 现在我们已经解决了元素关系问题。 基础3：集合合并 集合如何合并呢？基础2 中，我们已经可以找到元素对应集合的名称（即根节点标号），如果元素u、v（u、v 不在同一集合）对应的集合名称为_u、_v，那么语句 belg[_u]=_v 什么意思呢？想到了吧？就是把集合_u 与集合_v 合并，并且以_v 命名。 至此，通过基础部分我们知道了什么是并查集，通过精华提炼部分，我们知道了并查集的高级应用（精华提炼 2）。 三、优化 虽然我们已经知道了基础的并查集，但是大家有没有想过简单用上面介绍的集合合并可能造成集合（树）的退化。比如对只有一个元素的集合1 到集合n 进行下述操作：把集合1 合并到集合2，把集合2 合并到集合3，…… 把集合n-1 合并到集合n，那么生成一个含有n 各元素的集合n，它的结构如下： 那么，每次判断n 所属集合都要n 次操作，即复杂度为O(n )，这个耗费是不是必须的呢？其实不然。 优化 1：路径压缩 对于上图退化的集合，它的表示是这样的：belg[n ]=...
VIP
