Rollback Union-Find - Rollback 可能 Union-Find
(Library/DataStructure/RollbackUnionFind.hpp)

• View this file on GitHub
• Last update: 2025-04-30 01:32:17+09:00
• Include: #include "Library/DataStructure/RollbackUnionFind.hpp"

Rollback Union-Find - Rollback 可能 Union-Find

通常の Union-Find に加え、次の操作を可能としたデータ構造。

• 最後の Unite 操作の取り消し
• 予め記録した状態への復元

Function

Constructor

RollbackUnionFind(size_t n)

• $n$ 頂点 $0$ 辺の無向グラフを構築します。
• 頂点には $0, 1, \dots, n - 1$ の番号が振られているとします。

制約

• $0 \le n \le 10^6$

計算量

• $\textrm{O}(n)$

---

Find

int Find(const int k)

• 頂点 $k$ が属する連結成分の代表頂点を取得します。
• 内部処理として経路圧縮を行いません。

制約

• $0 \le k \lt n$

計算量

• $\textrm{O}(\log n)$

---

Same

bool Same(const int x, const int y)

• 頂点 $x$ と頂点 $y$ が連結であるかを判定します。
• 頂点 $x$ と頂点 $y$ が連結であるとき true を返します。

制約

• $0 \le x, y \lt n$

計算量

• $\textrm{O}(\log n)$

---

Unite

bool Unite(int x, int y)

• 頂点 $x$ と頂点 $y$ の間に辺 $(x, y)$ を追加します。
• 辺 $(x, y)$ の追加により頂点 $x$ と頂点 $y$ が連結になったとき true を返します。

制約

• $0 \le x, y \lt n$

計算量

• $\textrm{O}(\log n)$

---

Size

size_t Size(int k)

• 頂点 $k$ の属する連結成分の頂点数を返します。

制約

• $0 \le k \lt n$

計算量

• $\textrm{O}(\log n)$

---

Group

vector<vector<int>> Group()

• すべての連結成分に含まれる頂点の一覧を返します。

計算量

• $\textrm{O}(n \log n)$

---

Record

void Record()

• 現在のグラフの状態を記録します。
• 複数回呼び出した場合、最後に呼び出されたときの状態が記録されます。

計算量

• $\textrm{O}(1)$

---

Undo

void Undo()

• 最後の Unite 操作を取り消します。
• $1$ 回も操作を行っていない状態で呼び出したときの挙動は未定義です。

計算量

• $\textrm{O}(1)$

---

Rollback

void Rollback()

• Record で記録した状態まで Unite 操作を取り消します。
• Record を $1$ 度も呼び出していない場合はすべての操作を取り消します。
• 現在の状態が記録した状態より過去の状態である場合の挙動は未定義です。

計算量

• 取り消す Unite 操作の回数を $k$ として、$\textrm{O}(k)$

---

Depends on

• Library/Common.hpp

Verified with

• verify/AOJ-0723.test.cpp
• verify/LC-PersistentUnionfind.test.cpp

Code

#include "../Common.hpp"

class RollbackUnionFind{
    public:
    RollbackUnionFind(size_t n) : data_(n, -1), record_(0){}

    int Find(const int k) const {
        if(data_[k] < 0) return k;
        return Find(data_[k]);
    }

    bool Same(const int x, const int y) const {
        return Find(x) == Find(y);
    }

    bool Unite(int x, int y){
        x = Find(x), y = Find(y);
        history_.push({x, data_[x]});
        history_.push({y, data_[y]});
        if(x == y) return false;
        if(data_[x] > data_[y]) swap(x, y);
        data_[x] += data_[y];
        data_[y] = x;
        return true;
    }
    
    int Size(const int k) const {
        return -data_[Find(k)];
    }
    
    vector<vector<int>> Group() const {
        vector<vector<int>> ret(data_.size());
        for(int i = 0; i < data_.size(); ++i){
            ret[Find(i)].emplace_back(i);
        }
        ret.erase(remove_if(begin(ret), end(ret), [&](vector<int> &v){
            return v.empty();
        }), end(ret));
        return ret;
    }

    void Record(){
        record_ = history_.size();
    }

    void Undo(){
        auto [y, dy] = history_.top();
        history_.pop();
        data_[y] = dy;
        auto [x, dx] = history_.top();
        history_.pop();
        data_[x] = dx;
    }

    void Rollback(){
        int state = record_;
        while(state < (int)history_.size()) Undo();
    }
    
    private:
    vector<int> data_;
    stack<pair<int, int>> history_;
    int record_;
};

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 2 "Library/DataStructure/RollbackUnionFind.hpp"

class RollbackUnionFind{
    public:
    RollbackUnionFind(size_t n) : data_(n, -1), record_(0){}

    int Find(const int k) const {
        if(data_[k] < 0) return k;
        return Find(data_[k]);
    }

    bool Same(const int x, const int y) const {
        return Find(x) == Find(y);
    }

    bool Unite(int x, int y){
        x = Find(x), y = Find(y);
        history_.push({x, data_[x]});
        history_.push({y, data_[y]});
        if(x == y) return false;
        if(data_[x] > data_[y]) swap(x, y);
        data_[x] += data_[y];
        data_[y] = x;
        return true;
    }
    
    int Size(const int k) const {
        return -data_[Find(k)];
    }
    
    vector<vector<int>> Group() const {
        vector<vector<int>> ret(data_.size());
        for(int i = 0; i < data_.size(); ++i){
            ret[Find(i)].emplace_back(i);
        }
        ret.erase(remove_if(begin(ret), end(ret), [&](vector<int> &v){
            return v.empty();
        }), end(ret));
        return ret;
    }

    void Record(){
        record_ = history_.size();
    }

    void Undo(){
        auto [y, dy] = history_.top();
        history_.pop();
        data_[y] = dy;
        auto [x, dx] = history_.top();
        history_.pop();
        data_[x] = dx;
    }

    void Rollback(){
        int state = record_;
        while(state < (int)history_.size()) Undo();
    }
    
    private:
    vector<int> data_;
    stack<pair<int, int>> history_;
    int record_;
};

Back to top page