不相交集合

一组不相交的动态集合 S = { S1, S2, … , Sk } 每个集合通过一个代表来识别,即Si中的某个成员

森林表示法

       c            f           # S = { Sc, Sf }
      / \           |           # Sc = { c, h, e, b }
     h   e          d           # Sf = { f, d, g }
     |              |
     b              g

操作

MakeSet( x )

建立一个新的集合,其唯一成员(代表)是x,且x不在其他集合中

    MakeSet( x )
        parent[x] = x ;
        rank[x] = 0 ; :x到其后代叶节点最长路径的上限值
FindSet( x )

返回包x的集合的代表

    FindSet( x )                        // 第一次返回时,是x的代表
        if parent[x] != x                    // 第二次返回时,是parent[x],即x的代表
            parent[x] = FindSet( parent[x] ) ;    
        return parent[x] ;                   //最后返回parent[x]是x的代表
Union( x, y )

将包含x,y的集合,合并成一个新的集合

    Union( x, y )                               
        Link( FindSet( x ), FindSet( y ) ) ;    //按秩合并的 T(n) = O(mlgn)
    /*-----------------*/                   
    Link( x, y )                                //同时使用按秩合并和路径压缩
        if rand[x] > rank[y]                    //的最坏情况 T(n) = O( m*A(n))
            parent[y] = x ;                          //其中A(n) <= 4
        else
            parent[x] = y ;
            rank[x] = rand[y] ;
            rank[y]++ ;