Partially Persistent Union Find
(src/datastructure/PartiallyPersistentUnionFind.hpp)

• View this file on GitHub
• Last update: 2023-01-12 22:28:24+09:00
• Include: #include "src/datastructure/PartiallyPersistentUnionFind.hpp"

概要

経路圧縮を行わずにマージテクを利用して集合を管理する際に，変更される値が少ないことを利用してタイムスタンプを用いて過去の頂点の連結成分やその頂点数といったデータを取得できるようにしたデータ構造．

以下に記す内容について，時刻 $t$ は 0 からスタートし merge が呼び出されるごとに操作直前にインクリメントされる． すなわち $i$ 回目 (1-indexed) のマージ後の関係を調べるためには引数 $t$ はそのまま $i$ でよく，1-indexed であることに注意が必要である．

メンバ関数	効果	時間計算量
PartiallyPersistentUnionFind(n)	要素数 $n$ で初期化する．	$O(n)$
find(t, x)	時刻 $t$ において頂点 $x$ が属していた集合の代表元を返す．	$O(\log n)$
merge(x, y)	頂点 $x, y$ が属する集合を併合する．	$O(\log n)$
same(t, x, y)	時刻 $t$ において頂点 $x, y$ が同一の集合に属していたか判定する．	$O(\log n)$
size(t, x)	時刻 $t$ において頂点 $x$ が属していた集合の要素数を返す．	$O(\log n)$

問題例

• AtCoder Grand Contest 002 D - Stamp Rally

Links

• UnionFindTree に関する知見の諸々 - noshi91のメモ

Code

#pragma once
#include <cassert>
#include <limits>
#include <vector>

struct PartiallyPersistentUnionFind {
    PartiallyPersistentUnionFind(int n)
        : n(n), time(0), data(n, -1), last(n, std::numeric_limits<int>::max()), history(n) {
        for (auto& v : history) v.emplace_back(-1, -1);
    }

    int find(int t, int x) const {
        assert(0 <= x && x < n);
        return t < last[x] ? x : find(t, data[x]);
    }

    bool merge(int x, int y) {
        assert(0 <= x && x < n);
        assert(0 <= y && y < n);
        time++;
        if ((x = find(time, x)) == (y = find(time, y))) return false;
        if (-data[x] < -data[y]) std::swap(x, y);
        data[x] += data[y];
        history[x].emplace_back(time, data[x]);
        data[y] = x;
        last[y] = time;
        return true;
    }

    bool same(int t, int x, int y) const {
        assert(0 <= x && x < n);
        assert(0 <= y && y < n);
        return find(t, x) == find(t, y);
    }

    int size(int t, int x) const {
        assert(0 <= x && x < n);
        x = find(t, x);
        return -prev(lower_bound(history[x].begin(), history[x].end(), std::make_pair(t, 0)))->second;
    }

private:
    int n, time;
    std::vector<int> data, last;
    std::vector<std::vector<std::pair<int, int>>> history;
};

#line 2 "src/datastructure/PartiallyPersistentUnionFind.hpp"
#include <cassert>
#include <limits>
#include <vector>

struct PartiallyPersistentUnionFind {
    PartiallyPersistentUnionFind(int n)
        : n(n), time(0), data(n, -1), last(n, std::numeric_limits<int>::max()), history(n) {
        for (auto& v : history) v.emplace_back(-1, -1);
    }

    int find(int t, int x) const {
        assert(0 <= x && x < n);
        return t < last[x] ? x : find(t, data[x]);
    }

    bool merge(int x, int y) {
        assert(0 <= x && x < n);
        assert(0 <= y && y < n);
        time++;
        if ((x = find(time, x)) == (y = find(time, y))) return false;
        if (-data[x] < -data[y]) std::swap(x, y);
        data[x] += data[y];
        history[x].emplace_back(time, data[x]);
        data[y] = x;
        last[y] = time;
        return true;
    }

    bool same(int t, int x, int y) const {
        assert(0 <= x && x < n);
        assert(0 <= y && y < n);
        return find(t, x) == find(t, y);
    }

    int size(int t, int x) const {
        assert(0 <= x && x < n);
        x = find(t, x);
        return -prev(lower_bound(history[x].begin(), history[x].end(), std::make_pair(t, 0)))->second;
    }

private:
    int n, time;
    std::vector<int> data, last;
    std::vector<std::vector<std::pair<int, int>>> history;
};

Back to top page