Potential Union Find (potential_union_find.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-14 02:50:33+09:00
• Include: #include "potential_union_find.hpp"

UnionFind の頂点にポテンシャル $U(i)$ が追加された版。

コンストラクタ

PotentialUnionFind(int n)

頂点数 n で作成。

計算量

• $O(n)$

root

int root(int i)

i が属する連結成分の代表元を返す。

計算量

• $O(\log n)$

unite

bool unite(int i, int j, S x)

i と j を繋ぐ。

$U(i)-U(j)=x$ という条件について、

• 既存の条件と矛盾しない場合、この条件を追加し、true を返す。
• 矛盾している場合、この条件を破棄し、false を返す。

delta

optional<S> delta(int i, int j)

i と j が連結な場合、$U(i)-U(j)$ を返す。連結でない場合、nullopt を返す。

計算量

• $O(\log n)$

Verified with

• test/lc_unionfind_with_potential.cpp

Code

template <class S>
class PotentialUnionFind {
   public:
    PotentialUnionFind(int n_) : n(n_), par(n_), d(n_) { iota(par.begin(), par.end(), 0); }

    int root(int i) {
        assert(0 <= i && i < n);
        if (par[i] == i) return i;
        int p0 = root(par[i]);
        d[i] += d[par[i]];  // U[p0] - U[i] = (U[p0] - U[par[i]]) + (U[par[i]] - U[i])
        return par[i] = p0;
    }

    // U[i] - U[j] <- x
    bool unite(int i, int j, S x) {
        assert(0 <= i && i < n);
        assert(0 <= j && j < n);
        int r_i = root(i), r_j = root(j);
        if (r_i == r_j) return d[j] - d[i] == x;
        par[r_j] = r_i;
        d[r_j] = d[i] + x - d[j];
        //   U[par[r_j]] - U[r_j]
        // = U[r_i] - U[r_j]
        // = (U[r_i] - U[i]) + (U[i] - U[j]) - (U[r_j] - U[j])
        return true;
    }

    // U[i] - U[j]
    optional<S> delta(int i, int j) {
        assert(0 <= i && i < n);
        assert(0 <= j && j < n);
        int r_i = root(i), r_j = root(j);
        if (r_i != r_j) return nullopt;
        return d[j] - d[i];
    }

   private:
    int n;
    vector<int> par;
    vector<S> d;  // U[par[i]] - U[i]
};

#line 1 "potential_union_find.hpp"
template <class S>
class PotentialUnionFind {
   public:
    PotentialUnionFind(int n_) : n(n_), par(n_), d(n_) { iota(par.begin(), par.end(), 0); }

    int root(int i) {
        assert(0 <= i && i < n);
        if (par[i] == i) return i;
        int p0 = root(par[i]);
        d[i] += d[par[i]];  // U[p0] - U[i] = (U[p0] - U[par[i]]) + (U[par[i]] - U[i])
        return par[i] = p0;
    }

    // U[i] - U[j] <- x
    bool unite(int i, int j, S x) {
        assert(0 <= i && i < n);
        assert(0 <= j && j < n);
        int r_i = root(i), r_j = root(j);
        if (r_i == r_j) return d[j] - d[i] == x;
        par[r_j] = r_i;
        d[r_j] = d[i] + x - d[j];
        //   U[par[r_j]] - U[r_j]
        // = U[r_i] - U[r_j]
        // = (U[r_i] - U[i]) + (U[i] - U[j]) - (U[r_j] - U[j])
        return true;
    }

    // U[i] - U[j]
    optional<S> delta(int i, int j) {
        assert(0 <= i && i < n);
        assert(0 <= j && j < n);
        int r_i = root(i), r_j = root(j);
        if (r_i != r_j) return nullopt;
        return d[j] - d[i];
    }

   private:
    int n;
    vector<int> par;
    vector<S> d;  // U[par[i]] - U[i]
};

Back to top page