Partially Persistent DSU
(ds/dsu/partially_persistent_dsu.hpp)

View this file on GitHub
Last update: 2026-08-11 13:59:43+09:00
Include: #include "ds/dsu/partially_persistent_dsu.hpp"

Overview

PartiallyPersistentDsu is a Union-Find data structure that supports queries against old times after merges are applied. The update history is linear: merge(a, b) creates the next time, and queries can be asked at any time from 0 through the current time.

Time 0 is the initial state. Each call to merge, including a no-op merge inside one component, increases the time by one.

It uses union by size without path compression, because old parent paths must remain queryable.

Complexity Notation

N is the number of elements.
Q is the number of merge calls already made.

Methods

Method	Description	Complexity
`PartiallyPersistentDsu()`	Creates an empty DSU at time `0`.	$O(1)$
`explicit PartiallyPersistentDsu(int n)`	Creates `n` singleton sets at time `0`.	$O(N)$
`int size() const`	Returns the number of elements.	$O(1)$
`bool empty() const`	Returns whether the DSU has no elements.	$O(1)$
`void release()`	Releases the complete history and resets the object to an empty DSU at time `0`.	$O(N + Q)$
`int time() const`	Returns the current time.	$O(1)$
`bool merge(int a, int b)`	Advances time by one and merges the current sets containing `a` and `b`. Returns whether two different sets were merged.	$O(\log N)$
`bool same(int t, int a, int b) const`	Returns whether `a` and `b` were in the same set at time `t`.	$O(\log N)$
`bool same(int a, int b) const`	Equivalent to `same(time(), a, b)`.	$O(\log N)$
`int leader(int t, int a) const`	Returns the representative of the set containing `a` at time `t`.	$O(\log N)$
`int leader(int a) const`	Equivalent to `leader(time(), a)`.	$O(\log N)$
`int group_size(int t, int a) const`, `int size(int t, int a) const`	Returns the size of the set containing `a` at time `t`.	$O(\log N + \log Q)$
`int group_size(int a) const`, `int size(int a) const`	Equivalent to querying at the current time.	$O(\log N)$
`std::vector<std::vector<int>> groups(int t) const`	Returns all sets at time `t` as vectors of element indices.	$O(N \log N)$
`std::vector<std::vector<int>> groups() const`	Equivalent to `groups(time())`.	$O(N \log N)$

Example

#include "ds/dsu/partially_persistent_dsu.hpp"

#include <iostream>

int main() {
    m1une::ds::PartiallyPersistentDsu dsu(4);

    dsu.merge(0, 1); // time 1
    dsu.merge(2, 3); // time 2
    dsu.merge(1, 2); // time 3

    std::cout << dsu.same(1, 0, 2) << "\n"; // 0
    std::cout << dsu.same(3, 0, 2) << "\n"; // 1
    std::cout << dsu.size(2, 0) << "\n";    // 2
    std::cout << dsu.size(3, 0) << "\n";    // 4
}

Verified with

Code

#ifndef M1UNE_PARTIALLY_PERSISTENT_DSU_HPP
#define M1UNE_PARTIALLY_PERSISTENT_DSU_HPP 1

#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>

namespace m1une {
namespace ds {

struct PartiallyPersistentDsu {
   private:
    static constexpr int never = std::numeric_limits<int>::max();

    int _n;
    int _time;
    std::vector<int> parent;
    std::vector<int> parent_time;
    std::vector<std::vector<std::pair<int, int>>> size_history;

    static int check_size(int n) {
        assert(0 <= n);
        return n;
    }

    void check_time(int t) const {
        assert(0 <= t && t <= _time);
    }

   public:
    PartiallyPersistentDsu() : PartiallyPersistentDsu(0) {}

    explicit PartiallyPersistentDsu(int n)
        : _n(check_size(n)), _time(0), parent(_n, -1), parent_time(_n, never), size_history(_n) {
        for (int i = 0; i < _n; i++) size_history[i].emplace_back(0, 1);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    // Releases the complete history and resets this object to an empty DSU.
    void release() {
        _n = 0;
        _time = 0;
        std::vector<int>().swap(parent);
        std::vector<int>().swap(parent_time);
        std::vector<std::vector<std::pair<int, int>>>().swap(size_history);
    }

    int time() const {
        return _time;
    }

    int leader(int t, int a) const {
        check_time(t);
        assert(0 <= a && a < _n);
        while (parent_time[a] <= t) a = parent[a];
        return a;
    }

    int leader(int a) const {
        return leader(_time, a);
    }

    bool same(int t, int a, int b) const {
        check_time(t);
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(t, a) == leader(t, b);
    }

    bool same(int a, int b) const {
        return same(_time, a, b);
    }

    int group_size(int t, int a) const {
        int r = leader(t, a);
        const auto& h = size_history[r];
        auto it = std::upper_bound(h.begin(), h.end(), std::pair<int, int>(t, never));
        --it;
        return it->second;
    }

    int group_size(int a) const {
        return -parent[leader(a)];
    }

    int size(int t, int a) const {
        return group_size(t, a);
    }

    int size(int a) const {
        return group_size(a);
    }

    bool merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        ++_time;
        int x = leader(a), y = leader(b);
        if (x == y) return false;
        if (-parent[x] < -parent[y]) {
            std::swap(x, y);
        }
        parent[x] += parent[y];
        parent[y] = x;
        parent_time[y] = _time;
        size_history[x].emplace_back(_time, -parent[x]);
        return true;
    }

    std::vector<std::vector<int>> groups(int t) const {
        check_time(t);
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(t, i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }),
                     result.end());
        return result;
    }

    std::vector<std::vector<int>> groups() const {
        return groups(_time);
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_PARTIALLY_PERSISTENT_DSU_HPP

#line 1 "ds/dsu/partially_persistent_dsu.hpp"



#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>

namespace m1une {
namespace ds {

struct PartiallyPersistentDsu {
   private:
    static constexpr int never = std::numeric_limits<int>::max();

    int _n;
    int _time;
    std::vector<int> parent;
    std::vector<int> parent_time;
    std::vector<std::vector<std::pair<int, int>>> size_history;

    static int check_size(int n) {
        assert(0 <= n);
        return n;
    }

    void check_time(int t) const {
        assert(0 <= t && t <= _time);
    }

   public:
    PartiallyPersistentDsu() : PartiallyPersistentDsu(0) {}

    explicit PartiallyPersistentDsu(int n)
        : _n(check_size(n)), _time(0), parent(_n, -1), parent_time(_n, never), size_history(_n) {
        for (int i = 0; i < _n; i++) size_history[i].emplace_back(0, 1);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    // Releases the complete history and resets this object to an empty DSU.
    void release() {
        _n = 0;
        _time = 0;
        std::vector<int>().swap(parent);
        std::vector<int>().swap(parent_time);
        std::vector<std::vector<std::pair<int, int>>>().swap(size_history);
    }

    int time() const {
        return _time;
    }

    int leader(int t, int a) const {
        check_time(t);
        assert(0 <= a && a < _n);
        while (parent_time[a] <= t) a = parent[a];
        return a;
    }

    int leader(int a) const {
        return leader(_time, a);
    }

    bool same(int t, int a, int b) const {
        check_time(t);
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(t, a) == leader(t, b);
    }

    bool same(int a, int b) const {
        return same(_time, a, b);
    }

    int group_size(int t, int a) const {
        int r = leader(t, a);
        const auto& h = size_history[r];
        auto it = std::upper_bound(h.begin(), h.end(), std::pair<int, int>(t, never));
        --it;
        return it->second;
    }

    int group_size(int a) const {
        return -parent[leader(a)];
    }

    int size(int t, int a) const {
        return group_size(t, a);
    }

    int size(int a) const {
        return group_size(a);
    }

    bool merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        ++_time;
        int x = leader(a), y = leader(b);
        if (x == y) return false;
        if (-parent[x] < -parent[y]) {
            std::swap(x, y);
        }
        parent[x] += parent[y];
        parent[y] = x;
        parent_time[y] = _time;
        size_history[x].emplace_back(_time, -parent[x]);
        return true;
    }

    std::vector<std::vector<int>> groups(int t) const {
        check_time(t);
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(t, i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }),
                     result.end());
        return result;
    }

    std::vector<std::vector<int>> groups() const {
        return groups(_time);
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Partially Persistent DSU
(ds/dsu/partially_persistent_dsu.hpp)

Overview

Complexity Notation

Methods

Example

Verified with

Code

Partially Persistent DSU (ds/dsu/partially_persistent_dsu.hpp)

Overview

Complexity Notation

Methods

Example

Verified with

Code

Partially Persistent DSU
(ds/dsu/partially_persistent_dsu.hpp)