Undo-UnionFind(Undo付きUnionFind)
(graph/Undo-UnionFind.hpp)

• View this file on GitHub
• Last update: 2023-03-13 02:01:43+09:00
• Include: #include "graph/Undo-UnionFind.hpp"

説明

Undoが可能なUnionFindです

• Constructor

  UndoUnionFind(int n)
  

• 頂点x,yを接続

  bool unite(int x, int y)
  

• 同じ集合か判定

  bool same(int x, int y)
  

• その頂点を含む集合の大きさを求める

  int size(int x)
  

• 一つ前の状態に戻す

  void undo()
  

• 最初の状態に戻す

  void rollback()
  

• 現在の状態を保存する
• これ以降、rollbackした後はこの状態に戻る

  void snapshot()
  

Code

struct UndoUnionFind {
  private:
  int n;
  stack<pair<int,int>> hist;
  public:
  vector<int> d;
  UndoUnionFind(int n): n(n), d(n, -1){}
  int root(int x){
    assert(0 <= x && x < n);
    if(d[x] < 0) return x;
    return d[x] = root(d[x]);
  }
  bool unite(int x, int y){
    x = root(x);
    y = root(y);
    hist.emplace(x, d[x]);
    hist.emplace(y, d[y]);
    if(x == y) return false;
    if(d[x] > d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y){
    return root(x) == root(y);
  }
  int size(int x){
    return -d[root(x)];
  }
  void undo(){
    assert(!hist.empty());
    d[hist.top().first] = hist.top().second;
    hist.pop();
    d[hist.top().first] = hist.top().second;
    hist.pop();
  }
  void snapshot(){
    while(!hist.empty()) hist.pop();
  }
  void rollback(){
    while(!hist.empty()) undo();
  }
};

#line 1 "graph/Undo-UnionFind.hpp"
struct UndoUnionFind {
  private:
  int n;
  stack<pair<int,int>> hist;
  public:
  vector<int> d;
  UndoUnionFind(int n): n(n), d(n, -1){}
  int root(int x){
    assert(0 <= x && x < n);
    if(d[x] < 0) return x;
    return d[x] = root(d[x]);
  }
  bool unite(int x, int y){
    x = root(x);
    y = root(y);
    hist.emplace(x, d[x]);
    hist.emplace(y, d[y]);
    if(x == y) return false;
    if(d[x] > d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y){
    return root(x) == root(y);
  }
  int size(int x){
    return -d[root(x)];
  }
  void undo(){
    assert(!hist.empty());
    d[hist.top().first] = hist.top().second;
    hist.pop();
    d[hist.top().first] = hist.top().second;
    hist.pop();
  }
  void snapshot(){
    while(!hist.empty()) hist.pop();
  }
  void rollback(){
    while(!hist.empty()) undo();
  }
};

Back to top page