DataStructure/QuickFind.cpp

Back to top page

• category: DataStructure
• View this file on GitHub
  • Last commit date: 2020-05-14 17:59:14+09:00

Description

素集合を管理する。
find(x) : x の属する集合の root を返す。 O(1)
unite(u,v) : u,v それぞれが属する集合を併合する。 償却 O(log N)
size(x) : x の属する集合のサイズを返す。 O(1)
same(u,v) : u,v が同じ集合に属するか判定する。 O(1)
elements(u) : u を含む集合の vector を返す。 O(1)

Verified with

• Test/QuickFind.test.cpp

Code

//@docs Docs/QuickFind.md
struct QuickFind {
    int n;
    vector<vector<int>> vs;
    vector<int> root;
    QuickFind(int n) : n(n), vs(n), root(n) {
        iota(root.begin(), root.end(), 0);
        for (int i = 0; i < n; i++) {
            vs[i].emplace_back(i);
        }
    }
    inline int size(int u) {
        return vs[root[u]].size();
    }
    bool unite(int u, int v) {
        u = root[u], v = root[v];
        if (u == v) return false;
        if (size(u) < size(v)) swap(u, v);
        for (auto &e : vs[v]) {
            vs[u].emplace_back(e);
            root[e] = u;
        }
        return true;
    }
    inline int same(int u, int v) {
        return root[u] == root[v];
    }
    vector<int> &elements(int u) {
        return vs[root[u]];
    }
};

#line 1 "DataStructure/QuickFind.cpp"
//@docs Docs/QuickFind.md
struct QuickFind {
    int n;
    vector<vector<int>> vs;
    vector<int> root;
    QuickFind(int n) : n(n), vs(n), root(n) {
        iota(root.begin(), root.end(), 0);
        for (int i = 0; i < n; i++) {
            vs[i].emplace_back(i);
        }
    }
    inline int size(int u) {
        return vs[root[u]].size();
    }
    bool unite(int u, int v) {
        u = root[u], v = root[v];
        if (u == v) return false;
        if (size(u) < size(v)) swap(u, v);
        for (auto &e : vs[v]) {
            vs[u].emplace_back(e);
            root[e] = u;
        }
        return true;
    }
    inline int same(int u, int v) {
        return root[u] == root[v];
    }
    vector<int> &elements(int u) {
        return vs[root[u]];
    }
};

Back to top page