Partially Persistent Union Find
(data-structure/unionfind/partially_persistent_union_find.hpp)

• View this file on GitHub
• Last update: 2024-01-07 20:49:49+09:00
• Include: #include "data-structure/unionfind/partially_persistent_union_find.hpp"

Description

部分永続 union find は素集合森の過去の連結性に関する情報を保持する．以下の操作を提供する:

• 2つの集合を連結する
• 時刻 $t$ で2つの要素が同じ集合に属していたか判定する
• 時刻 $t$ での集合の大きさを返す

空間計算量: $O(n + q)$

Operations

• PartiallyPersistentUnionFind(int n)
  • サイズnの部分永続 union find を構築する．時刻の初期値は 0 である．
  • 時間計算量: $O(n)$
• int find(int t, int x)
  • 時刻 $t$ で $x$ が属する木の根を返す
  • 時間計算量: $O(\log n)$
• void unite(int x, int y)
  • 時刻を 1 増加させ，$x$ が属する集合と $y$ が属する集合を連結する
  • 時間計算量: $O(\log n)$
• bool same(int t, int x, int y)
  • 時刻 $t$ で $x$ と $y$ が同じ集合に属するかを判定する
  • 時間計算量: $O(\log n)$
• int size(int t, int x)
  • 時刻 $t$ で $x$ が属する集合の大きさを返す
  • 時間計算量: $O(\log n)$

Reference

• 部分永続Union-Find Treeについて
• verify: https://atcoder.jp/contests/agc002/submissions/31059136

Code

#pragma once
#include <algorithm>
#include <limits>
#include <utility>
#include <vector>

class PartiallyPersistentUnionFind {
   public:
    PartiallyPersistentUnionFind() = default;
    explicit PartiallyPersistentUnionFind(int n)
        : data(n, -1), time(n, INF), sz(n, {{0, 1}}) {}

    int find(int t, int x) const {
        if (t < time[x]) return x;
        return find(t, data[x]);
    }

    void unite(int x, int y) {
        ++now;
        x = find(now, x);
        y = find(now, y);
        if (x == y) return;
        if (data[x] > data[y]) std::swap(x, y);
        data[x] += data[y];
        sz[x].emplace_back(now, -data[x]);
        data[y] = x;
        time[y] = now;
    }

    bool same(int t, int x, int y) const { return find(t, x) == find(t, y); }

    int size(int t, int x) const {
        x = find(t, x);
        return (--std::ranges::lower_bound(sz[x], std::make_pair(t, INF)))
            ->second;
    }

   private:
    static constexpr int INF = std::numeric_limits<int>::max();

    std::vector<int> data;
    std::vector<int> time;
    std::vector<std::vector<std::pair<int, int>>> sz;
    int now = 0;
};

#line 2 "data-structure/unionfind/partially_persistent_union_find.hpp"
#include <algorithm>
#include <limits>
#include <utility>
#include <vector>

class PartiallyPersistentUnionFind {
   public:
    PartiallyPersistentUnionFind() = default;
    explicit PartiallyPersistentUnionFind(int n)
        : data(n, -1), time(n, INF), sz(n, {{0, 1}}) {}

    int find(int t, int x) const {
        if (t < time[x]) return x;
        return find(t, data[x]);
    }

    void unite(int x, int y) {
        ++now;
        x = find(now, x);
        y = find(now, y);
        if (x == y) return;
        if (data[x] > data[y]) std::swap(x, y);
        data[x] += data[y];
        sz[x].emplace_back(now, -data[x]);
        data[y] = x;
        time[y] = now;
    }

    bool same(int t, int x, int y) const { return find(t, x) == find(t, y); }

    int size(int t, int x) const {
        x = find(t, x);
        return (--std::ranges::lower_bound(sz[x], std::make_pair(t, INF)))
            ->second;
    }

   private:
    static constexpr int INF = std::numeric_limits<int>::max();

    std::vector<int> data;
    std::vector<int> time;
    std::vector<std::vector<std::pair<int, int>>> sz;
    int now = 0;
};

Back to top page