Partial Persistent Union Find

コードについての説明

部分永続 Union Find の実装である.
部分永続データ構造とは過去のすべてのバージョンの参照および現在のバージョンの更新を行うことできるデータ構造のことを言う(過去のバージョンを参照できるというところが普通のデータ構造と異なる). 過去のバージョンも更新することができるようなものを完全永続データ構造と呼ぶ.
経路圧縮を行わない場合は各クエリ最悪 $\O (\log n)$ 時間で応答するデータ構造を簡単に実装できる. ポイントは Union find 森の親が $1$ 度できるとその後変化しないので, 各頂点について親ができた時間とその親の頂点の $2$ つを保持しておけば, あとは参照(同じ連結成分に属するかの判定)するときにその情報をもとに木の親をたどっていけば高々 $\O (\log n)$ 回でその時点での親にたどり着く. このとき, 親に向かう辺のできた時間は単調であることと rank の大きいものに小さいものを unite した場合高さは常に $\O (\log n)$ になるという事実を使っている.
size も併合の更新があった際に新しい値に (時間, 新しい木のサイズ) の情報を vector として持たせておけば, 参照時に根のもつ vector を $2$ 分探索することで結果を求められる.
少し考えてみると Find 操作は頂点と親を結ぶパス上の $2$ 分探索で求めることもできるのでダブリングの要領でならし計算量 $\O (\log \log n)$ も達成できる. さらに union find 森の構造(高さ $h$ の頂点は高々 $n / 2^h$ 個しかないという性質) に注目して, 各頂点にダブリングのように $\O (\log \log n)$ 個の頂点ではなくいい感じに間引いて配置することで空間計算量 $\O (n)$ でも可能になった(実装が結構めんどくなりそうだったのでもう少しいい方法があるかもしれない). この場合 size はまあ y-fast-trie を使えば期待計算量ではあるものの $\O (\log \log n)$ でできる(無理矢理感すごい).
論文を調べてみると, 経路圧縮と永続化は(特殊な)永続配列を用いて両立させることができるらしく, こちら にその話がある.
ちなみに部分永続化より真に難しい retroactive union find も効率よく行うことができる.

(関数)
find$(u)$ : 時刻 $\_ time$ の直後において $u$ を含む木の根を答える. unite$(u, v, \_ time)$ : 時刻 $\_ time$ において $u$ と $v$ を同じ連結成分にする. (ただし部分永続なので $\_ time$ は最後に unite を呼び出した時間以降とする.)
same$(u, v, \_ time)$ : 時刻 $\_ time$ の直後において $u$ と $v$ が同じ連結成分に入っているかを判定する. size$(u, \_ time)$ : 時刻 $\_ time$ の直後において $u$ を含む木の頂点数を答える.

時間計算量: $\O (\log n)$

コード

class PartialPersistentUnionFind {
public:
    const int V;
    int last;
    vector<pair<int, int> > par;
    vector<vector<pair<int, int> > > sz;
    PartialPersistentUnionFind(const int node_size)
        : V(node_size), last(numeric_limits<int>::min()), par(V), sz(V){
        for(int i = 0; i < V; ++i){
            par[i] = {numeric_limits<int>::max(), i};
            sz[i].emplace_back(numeric_limits<int>::min(), 1);
        }
    }
    int find(int u, const int _time){
        while(par[u].first <= _time) u = par[u].second;
        return u;
    }
    bool unite(int u, int v, const int _time){
        assert(last <= _time);
        last = _time;
        u = find(u, _time), v = find(v, _time);
        if(u == v) return false;
        if(sz[u].back().first < sz[v].back().first) swap(u, v);
        par[v] = {_time, u};
        sz[u].emplace_back(_time, sz[u].back().second + sz[v].back().second);
        return true;
    }
    bool same(const int u, const int v, const int _time){
        return find(u, _time) == find(v, _time);
    }
    int size(int u, const int _time){
        u = find(u, _time);
        return sz[u][static_cast<int>(upper_bound(sz[u].begin(), sz[u].end(),
            make_pair(_time, V + 1)) - sz[u].begin()) - 1].second;
    }
};

verify 用の問題

Atcoder : Union Sets 提出コード(size 以外の verify)
Atcoder : Stamp Rally 提出コード