UnionFind
(library/structure/UnionFind/UnionFind.cpp)

• View this file on GitHub
• Last update: 2020-11-14 13:19:56+09:00

Required by

• library/structure/UnionFind/merge_tree.cpp

Verified with

• verify/aoj-dsl-1-a.test.cpp

Code

/**
 * @brief UnionFind
 * @docs docs/UnionFind.md
 */
struct UnionFind {
    vector<int> data;  // sizes of sets

    UnionFind(int sz) : data(sz, -1) {}

    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return true;
    }

    int find(int k) {
        if (data[k] < 0) return k;
        return data[k] = find(data[k]);
    }

    int size(int k) { return (-data[find(k)]); }

    bool same(int x, int y) { return find(x) == find(y); }
};

#line 1 "library/structure/UnionFind/UnionFind.cpp"

/**
 * @brief UnionFind
 * @docs docs/UnionFind.md
 */
struct UnionFind {
    vector<int> data;  // sizes of sets

    UnionFind(int sz) : data(sz, -1) {}

    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return true;
    }

    int find(int k) {
        if (data[k] < 0) return k;
        return data[k] = find(data[k]);
    }

    int size(int k) { return (-data[find(k)]); }

    bool same(int x, int y) { return find(x) == find(y); }
};

Back to top page