kkogoro

并查集模板
并查集模板普通并查集路径压缩namespace UNION { int fa[MAXN]; inl...
扫描右侧二维码阅读全文
08
2018/11

并查集模板

并查集模板

普通并查集

路径压缩

namespace UNION {
    int fa[MAXN];
    inline void init(int n) {
        for (int i = 1; i <= n; ++i) {
            fa[i] = i;
        }
        return;
    }
    int get(int x) {
        return fa[x] == x ? x : fa[x] = get(fa[x]);
    }
    inline void merge(int x, int y) {
        x = get(x);
        y = get(y);
        if (x != y) {
            fa[x] = y;
        }
        return;
    }
}

路径压缩+按秩合并

namespace UNION {
    int fa[MAXN], size[MAXN];
    inline void init(int n) {
        for (int i = 1; i <= n; ++i) {
            fa[i] = i;
            size[i] = 1;
        }
        return;
    }
    int get(int x) {
        return fa[x] == x ? x : fa[x] = get(fa[x]);
    }
    inline void merge(int x, int y) {
        x = get(x);
        y = get(y);
        if (x != y) {
            if (size[x] < size[y]) {
                size[y] += size[x];
                fa[x] = y;
            }
            else {
                size[x] += size[y];
                fa[y] = x;
            }
        }
        return;
    }
}

单数组

namespace UNION {
    int fa[MAXN];
    inline void init() {
        memset(fa, -1, sizeof fa);
        return;
    }
    int get(int x) {
        return fa[x] < 0 ? x : fa[x] = get(fa[x]);
    }
    inline void merge(int x, int y) {
        x = get(x);
        y = get(y);
        if (x != y) {
            if (fa[x] > fa[y]) {
                fa[y] += fa[x];
                fa[x] = y;
            }
            else {
                fa[x] += fa[y];
                fa[y] = x;
            }
        }
        return;
    }
    inline int size(int x) {
        x = get(x);
        return -fa[x];
    }
}

带权并查集

洛谷P1196 [NOI2002]银河英雄传说

#include <iostream>
#include <cstdio>


const int MAXN = 30007;



namespace UNION {
    int fa[MAXN], dist[MAXN], size[MAXN];
    inline void init(int n) {
        for (int i = 1; i <= n; ++i) {
            fa[i] = i;
            dist[i] = 0;
            size[i] = 1;
        }
        return;
    }
    int get(int x) {
        if (fa[x] == x) return x;
        int tmp_fa = fa[x];
        fa[x] = get(fa[x]);
        dist[x] += dist[tmp_fa];
        return fa[x];
    }
    inline void merge(int x, int y) {
        x = get(x);
        y = get(y);
        if (x != y) {
            fa[x] = y;
            dist[x] = size[y];
            size[y] += size[x];
        }
    }
}


inline int ABS(int a) {
    return a < 0 ? -a : a;
}


int main() {
    int T;
    char opt[3];
    scanf("%d", &T);
    UNION::init(MAXN - 1);
    for (int i = 1; i <= T; ++i) {
        int x, y;
        scanf("%s%d%d", opt, &x, &y);
        if (opt[0] == 'M') {
            UNION::merge(x, y);
        }
        else {
            if (UNION::get(x) == UNION::get(y)) {
                printf("%d\n", ABS(UNION::dist[x] - UNION::dist[y]) - 1);
            }
            else {
                printf("-1\n");
            }
        }
    }
    return 0;
}
Last modification:November 8th, 2018 at 02:21 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment