首页 > 试题广场 >

写出一个包含m个MAKE-SET,UNION和FIND-SE

[问答题]
写出一个包含m个MAKE-SET,UNION和FIND-SET操作的序列(其中有n个是MAKE-SET操作),当仅使用按秩合并时,需要的时间。
MAKE-SET(v){
    x.p = x
    x.rank = 0
}
UNION(u,v){
    LINK(FIND-SET(u),== FIND-SET(v))
}
LINK(x,y){
    if x.rank > y.rank
        y.p = x
    else
        x.p = y
        if x.rank == y.rank
            y.rank++
}
FIND-SET(x){
    if x != x.p
        x.p = FIND-SET(x.p)
    return x.p
}

这道题你会答吗?花几分钟告诉大家答案吧!