并查集模版

本文最后更新于：2022年7月3日 下午

版本一：加权快速合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int[] father;
int[] sz;
int num;

public int find(int p) {
    if (p != father[p]) {
        p = find(father[p]);
    }
    return p;
}
public void union(int p, int q) {
    int i = find(p);
    int j = find(q);
    if (i == j) return;
    num -= 1;
    if (sz[i] < sz[j]) {
        father[i] = j;
        sz[j] += sz[i];
    } else {
        father[j] = i;
        sz[i] += sz[j];
    }
}

public void initUF(int n) {
    father = new int[n];
    sz = new int[n];
    num = n;
    for (int i = 0; i < n; i++) {
        father[i] = i;
        sz[i] = 1;
    }
}

版本二：路径压缩的加权快速合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int[] father;
int[] sz;
int num;
public int find(int p) {
    if (p != father[p]) {
        father[p] = find(father[p]);
    }
    return father[p];
}
public void union(int p, int q) {
    int i = find(p);
    int j = find(q);
    if (i == j) return;
    num -= 1;
    if (sz[i] < sz[j]) {
        father[i] = j;
        sz[j] += sz[i];
    } else {
        father[j] = i;
        sz[i] += sz[j];
    }
}

public void initUF(int n) {
    father = new int[n];
    sz = new int[n];
    num = n;
    for (int i = 0; i < n; i++) {
        father[i] = i;
        sz[i] = 1;
    }
}

自己的并查集模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class UnionFind{
        public int num;
        public int[] father;
        public int[] depth;
        public UnionFind(int n){
            num=n;
            father=new int[n];
            depth=new int[n];
            for(int i=0;i<n;i++){
                father[i]=i;
                depth[i]=1;
            }

        }

        public boolean merge(int i,int j){
            int rootX=find(i);
            int rootY=find(j);
            if(rootX==rootY){
                return false;
            }
            if(depth[rootX]>depth[rootY]){
                father[rootY]=rootX;
                depth[rootX]+=depth[rootY];
            }else{
                father[rootX]=rootY;
                depth[rootY]+=depth[rootX];
            }
            num--;
            return true;
        }

        public int find(int i){
            if(father[i]!=i){
                father[i]=find(father[i]);
            }
            return father[i];
        }
}
算法
#算法
并查集模版
https://dlddw.xyz/2022/07/01/并查集模板/
作者
Deepblue
发布于
2022年7月1日
许可协议