Undoable Union Find
(data-structure/unionfind/undoable_union_find.hpp)

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

Description

Undo 可能 union find は，直前の変更の破棄が可能な union find である．変更前の値を保存しておき，経路圧縮をしないことによって操作前の状態の復元が可能となる．また，連結成分の頂点の値 (可換モノイド) の総和の取得も可能である．

空間計算量: $O(n + m)$, $m$ は操作回数

Operations

• UndoableUnionFind(int n)
  • サイズnで頂点の値がすべて単位元 $e$ の undo 可能 union find を構築する
  • 時間計算量: $O(n)$
• UndoableUnionFind(vector<T> v)
  • vの要素からサイズn = v.size()の undo 可能 union find を構築する
  • 時間計算量: $O(n)$
• int find(int x)
  • $x$ が属する木の根を返す
  • 時間計算量: $O(\log n)$
• void unite(int x, int y)
  • $x$ が属する集合と $y$ が属する集合を連結する
  • 時間計算量: $O(\log n)$
• void undo()
  • 操作を undo する．
  • 時間計算量: $O(1)$
• bool same(int x, int y)
  • $x$ と $y$ が同じ集合に属するかを判定する
  • 時間計算量: $O(\log n)$
• int size(int x)
  • $x$ が属する集合の大きさを返す
  • 時間計算量: $O(\log n)$
• T component_fold(int x)
  • $x$ が属する連結成分の頂点の値を fold する
  • 時間計算量: $O(1)$
• void update(int x, T v)
  • $a_x$ を $a_x \cdot v$ に更新する
  • 時間計算量: $O(1)$

Required by

• Offline Dynamic Connectivity (graph/offline_dynamic_connectivity.hpp)

Verified with

• test/yosupo/dynamic_graph_vertex_add_component_sum.test.cpp

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <stack>
#include <utility>
#include <vector>

template <typename M>
class UndoableUnionFind {
    using T = M::T;

   public:
    UndoableUnionFind() = default;
    explicit UndoableUnionFind(int n)
        : UndoableUnionFind(std::vector<T>(n, M::id())) {}
    explicit UndoableUnionFind(const std::vector<T>& v)
        : data(v.size(), -1), val(v.begin(), v.end()) {}

    int find(int x) const {
        if (data[x] < 0) return x;
        return find(data[x]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        history.emplace(-1, 0, M::id());
        history.emplace(x, data[x], val[x]);
        history.emplace(y, data[y], val[y]);
        if (x == y) return;
        if (data[x] > data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
        val[x] = M::op(val[x], val[y]);
    }

    void undo() {
        assert(!history.empty());
        while (true) {
            auto [x, dx, vx] = history.top();
            history.pop();
            if (x == -1) break;
            data[x] = dx;
            val[x] = vx;
        }
    }

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

    int size(int x) const { return -data[find(x)]; }

    T component_fold(int x) const { return val[find(x)]; }

    void update(int x, const T& v) {
        x = find(x);
        history.emplace(-1, 0, M::id());
        history.emplace(x, data[x], val[x]);
        val[x] = M::op(val[x], v);
    }

   private:
    std::vector<int> data;
    std::vector<T> val;
    std::stack<std::tuple<int, int, T>> history;
};

#line 2 "data-structure/unionfind/undoable_union_find.hpp"
#include <algorithm>
#include <cassert>
#include <stack>
#include <utility>
#include <vector>

template <typename M>
class UndoableUnionFind {
    using T = M::T;

   public:
    UndoableUnionFind() = default;
    explicit UndoableUnionFind(int n)
        : UndoableUnionFind(std::vector<T>(n, M::id())) {}
    explicit UndoableUnionFind(const std::vector<T>& v)
        : data(v.size(), -1), val(v.begin(), v.end()) {}

    int find(int x) const {
        if (data[x] < 0) return x;
        return find(data[x]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        history.emplace(-1, 0, M::id());
        history.emplace(x, data[x], val[x]);
        history.emplace(y, data[y], val[y]);
        if (x == y) return;
        if (data[x] > data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
        val[x] = M::op(val[x], val[y]);
    }

    void undo() {
        assert(!history.empty());
        while (true) {
            auto [x, dx, vx] = history.top();
            history.pop();
            if (x == -1) break;
            data[x] = dx;
            val[x] = vx;
        }
    }

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

    int size(int x) const { return -data[find(x)]; }

    T component_fold(int x) const { return val[find(x)]; }

    void update(int x, const T& v) {
        x = find(x);
        history.emplace(-1, 0, M::id());
        history.emplace(x, data[x], val[x]);
        val[x] = M::op(val[x], v);
    }

   private:
    std::vector<int> data;
    std::vector<T> val;
    std::stack<std::tuple<int, int, T>> history;
};

Back to top page