biscuitの博客

1
int Find(int x){
2
    if (p[x]==x)
3
        return x
4
    else
5
        retutn Find(p[x])
6
        //retutn p[x]=Find(p[x]) //路径压缩，扁平化
7
}

1
h[int 根节点值]=树高
2

3
void Union(int x,int y){
4
    int rootx=Find(x)
5
    int rooty=Find(y)
6
    if (rootx!=rooty){
7
        p[rootx]=p[rooty]//或者p[rooty]=p[rootx]
8
    }
9
}
10

11

12
void UnionWithHeight(int x,int y){
13
    int rootx=Find(x)
14
    int rooty=Find(y)
15
    if (rootx!=rooty){
16
        if(h[rootx]<h[rooty]){
17
        p[rootx]=p[rooty]//矮树合并到高树
18
        }
19
        if(h[rootx]>h[rooty]){
20
        p[rooty]=p[rootx]//高树合并到矮树
21
        }
22
        else{
23
            p[rootx]=p[rooty]
24
            h[rooty]++
25
        }
26
    }
27
}