常用算法模板

朴素并查集模板

Java版

int[] p;
public void test() {
    // 初始化，p存储每个点的父节点
    int n = 10;
    p = new int[n];
    for (int i = 0; i < n; i++) {
        p[i] = i;
    }
}
// 返回x的祖宗节点
public int find(int x) {
    if (p[x] != x) {
        // 路径压缩
        p[x] = find(p[x]);
    }
    return p[x];
}
// 合并a和b所在的两个集合
public void union(int a, int b){
    p[find(a)] = find(b);
}

维护size的并查集模板

Java版

int[] p;
int[] size;
public void test() {
    // 初始化，p存储每个点的父节点
    int n = 10;
    p = new int[n];
    for (int i = 0; i < n; i++) {
        p[i] = i;
    }
    // size只有当节点是祖宗节点时才有意义，表示祖宗节点所在的集合中，点的数量
    size = new int[n];
    Arrays.fill(size, 1);

}
// 返回x的祖宗节点
public int find(int x) {
    if (p[x] != x) {
        // 路径压缩
        p[x] = find(p[x]);
    }
    return p[x];
}
// 合并a和b所在的两个集合
public void union(int a, int b){
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);
}

维护到祖宗节点距离的并查集模板

Java版

int[] p;
int[] d;
public void test() {
    // 初始化，p存储每个点的父节点
    int n = 10;
    p = new int[n];
    for (int i = 0; i < n; i++) {
        p[i] = i;
    }
    // d[x]存储x到p[x]的距离
    d = new int[n];

}
// 返回x的祖宗节点
public int find(int x) {
    if (p[x] != x) {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}
// 合并a和b所在的两个集合
public void union(int a, int b){
    p[find(a)] = find(b);
    // d[find(a)] = distance;
}

我开源了一份武林秘籍，欢迎⭐️star：

• https://gitee.com/lexiaoyuan/the-priceless-treasure-of-wulin
• https://github.com/lexiaoyuan/The-Priceless-Treasure-of-Wulin

创作不易，喜欢的话加个关注点个赞，❤谢谢谢谢❤