UndoUnionFindTree - Undoつき Union Find Tree
(lib/41-union-find-tree/UndoUnionFindTree.cpp)

• View this file on GitHub
• Last update: 2023-06-19 01:52:47+09:00

UndoUnionFindTree

• Undo付きunion find
• 経路圧縮をせず、mergeの履歴を持つことで、undoができるunion find

コンストラクタ

• UndoUnionFindTree(int N = 1, T ini = 0)
  • Nは頂点数

メソッド

• inline bool connected(int n, int m)
  • 連結判定
  • $O(\log N)$
• bool merge(int n, int m)
  • $O(\log N)$
• inline int operator
  • 頂点nの根を返す
• inline void print()
  • デバッグ用

Verified with

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

Code

/*
 * @title UndoUnionFindTree - Undoつき Union Find Tree
 * @docs md/union-find-tree/UndoUnionFindTree.md
 */
class UndoUnionFindTree {
    vector<int> parent;
    stack<array<int,2>> history;
    inline int root(int n) {
        return (parent[n]<0?n:root(parent[n]));
    }
public:
    UndoUnionFindTree(const int N = 1) : parent(N,-1){
    }
    inline bool connected(const int n, const int m) {
        return root(n) == root(m);
    }
    inline void merge(int n,int m) {
        n = root(n);
        m = root(m);
        history.push({n,parent[n]});
        history.push({m,parent[m]});
        if (n == m) return;
        if(parent[n]>parent[m]) swap(n, m);
        parent[n] += parent[m];
        parent[m] = n;
    }
    inline int size(const int n){
        return (-parent[root(n)]);
    }
    inline int operator[](const int n) {
        return root(n);
    }
    inline void print() {
        for(int i = 0; i < parent.size(); ++i) cout << root(i) << " ";
        cout << endl;
    }
    inline void undo() {
        for(int i=0;i<2;++i) {
            auto ar=history.top(); history.pop();
            parent[ar[0]]=ar[1];
        }
    }
};

#line 1 "lib/41-union-find-tree/UndoUnionFindTree.cpp"
/*
 * @title UndoUnionFindTree - Undoつき Union Find Tree
 * @docs md/union-find-tree/UndoUnionFindTree.md
 */
class UndoUnionFindTree {
    vector<int> parent;
    stack<array<int,2>> history;
    inline int root(int n) {
        return (parent[n]<0?n:root(parent[n]));
    }
public:
    UndoUnionFindTree(const int N = 1) : parent(N,-1){
    }
    inline bool connected(const int n, const int m) {
        return root(n) == root(m);
    }
    inline void merge(int n,int m) {
        n = root(n);
        m = root(m);
        history.push({n,parent[n]});
        history.push({m,parent[m]});
        if (n == m) return;
        if(parent[n]>parent[m]) swap(n, m);
        parent[n] += parent[m];
        parent[m] = n;
    }
    inline int size(const int n){
        return (-parent[root(n)]);
    }
    inline int operator[](const int n) {
        return root(n);
    }
    inline void print() {
        for(int i = 0; i < parent.size(); ++i) cout << root(i) << " ";
        cout << endl;
    }
    inline void undo() {
        for(int i=0;i<2;++i) {
            auto ar=history.top(); history.pop();
            parent[ar[0]]=ar[1];
        }
    }
};

Back to top page