PotentializedUnionFindTree - ポテンシャル付きUnionFind木
(lib/41-union-find-tree/PotentializedUnionFindTree.cpp)

• View this file on GitHub
• Last update: 2023-06-17 04:07:32+09:00

PotentializedUnionFindTree

• ポテンシャル付きunion find

コンストラクタ

• PotentializedUnionFindTree(int N = 1, T ini = 0)
  • Nは頂点数
  • Tはポテンシャルの初期値

メソッド

• inline bool connected(int n, int m)
  • 連結判定
  • そこそこ高速
• bool merge(int n, int m, T d=0)
  • $ potential[m] = potential[n] + d $ となるようにマージする
  • そこそこ高速
  • 既に連結のときは未定義 falseが返る
• T diff(int n, int m)
  • potential[m] - potential[n]を計算
  • 連結ではないときは未定義
• inline int operator
  • 頂点nの根を返す
• inline void print()
  • デバッグ用

参考資料

• 重み付き Union-Find 木とそれが使える問題のまとめ、および、牛ゲーについて
• People on a Line

Verified with

• test/union-find-tree/PotentializedUnionFindTree.test.cpp

Code

/*
 * @title PotentializedUnionFindTree - ポテンシャル付きUnionFind木
 * @docs md/union-find-tree/PotentializedUnionFindTree.md
 */
template<class T> class PotentializedUnionFindTree {
    vector<int> parent,rank;
    vector<T> potential;
    inline int root(int n) {
        if (parent[n] == n) {
            return n;
        }
        else {
            int r = root(parent[n]);
            potential[n] += potential[parent[n]];
            return parent[n] = r;
        }
    }
    inline T updated_dist(int x) {
        root(x);
        return potential[x];
    }
public:
    PotentializedUnionFindTree(int N = 1, T ini = 0) : parent(N),rank(N,1),potential(N,ini) {
        iota(parent.begin(),parent.end(),0);
    }
    inline bool connected(int n, int m) {
        return root(n) == root(m);
    }
    /*
    * potential[m] = potential[n] + dとなるようにマージする
    */
    bool merge(int n, int m, T d=0) {
        d += updated_dist(n);
        d -= updated_dist(m);
        n = root(n); m = root(m);
        if (n == m) return false;
        if (rank[n] < rank[m]) {
            swap(n, m);
            d = -d;
        }
        if (rank[n] == rank[m]) ++rank[n];
        parent[m] = n;
        potential[m] = d;
        return true;
    }
    /*
    * potential[m] - potential[n]
    */
    T diff(int n, int m) {
        return updated_dist(m) - updated_dist(n);
    }
    inline int operator[](int n) {
        return root(n);
    }
    inline void print() {
        for(int i = 0; i < parent.size(); ++i) cout << root(i) << " ";
        cout << endl;
    }
};

#line 1 "lib/41-union-find-tree/PotentializedUnionFindTree.cpp"
/*
 * @title PotentializedUnionFindTree - ポテンシャル付きUnionFind木
 * @docs md/union-find-tree/PotentializedUnionFindTree.md
 */
template<class T> class PotentializedUnionFindTree {
    vector<int> parent,rank;
    vector<T> potential;
    inline int root(int n) {
        if (parent[n] == n) {
            return n;
        }
        else {
            int r = root(parent[n]);
            potential[n] += potential[parent[n]];
            return parent[n] = r;
        }
    }
    inline T updated_dist(int x) {
        root(x);
        return potential[x];
    }
public:
    PotentializedUnionFindTree(int N = 1, T ini = 0) : parent(N),rank(N,1),potential(N,ini) {
        iota(parent.begin(),parent.end(),0);
    }
    inline bool connected(int n, int m) {
        return root(n) == root(m);
    }
    /*
    * potential[m] = potential[n] + dとなるようにマージする
    */
    bool merge(int n, int m, T d=0) {
        d += updated_dist(n);
        d -= updated_dist(m);
        n = root(n); m = root(m);
        if (n == m) return false;
        if (rank[n] < rank[m]) {
            swap(n, m);
            d = -d;
        }
        if (rank[n] == rank[m]) ++rank[n];
        parent[m] = n;
        potential[m] = d;
        return true;
    }
    /*
    * potential[m] - potential[n]
    */
    T diff(int n, int m) {
        return updated_dist(m) - updated_dist(n);
    }
    inline int operator[](int n) {
        return root(n);
    }
    inline void print() {
        for(int i = 0; i < parent.size(); ++i) cout << root(i) << " ";
        cout << endl;
    }
};

Back to top page