UnionFind with Undo operation, monoid weights （Undo 可能・重み和取得可能 UnionFind）
(unionfind/undo_monoid_unionfind.hpp)

• View this file on GitHub
• Last update: 2022-10-11 22:40:37+09:00
• Include: #include "unionfind/undo_monoid_unionfind.hpp"

Undo 操作が可能な UnionFind．もともと同じ連結成分に属する元同士の unite() も操作一回に数える．

また，各要素に重みを与え，連結成分の重み総和取得も可能．undo_dsu<class S> として与えるクラス S は以下のように operator+= が定義されている必要がある：

struct S {
    S &operator+=(const S &x);
};

undo_dsu<S> dsu;

経路圧縮を行わないため，find() の計算量はクエリあたり $O(n \log n)$ となる．

使用方法

vector<int> a{2, 3, 4, 5};
undo_dsu<int> uf(a);

uf.unite(0, 2);
uf.undo();
uf.unite(0, 1);
uf.count(0);
uf.sum(0);
uf.reset();

Verified with

• data_structure/test/dynamic_graph_vertex_add_component_sum.test.cpp

Code

#pragma once
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>

// UnionFind, able to rewind to the previous state by undo()
template <class S> struct undo_dsu {
    std::vector<int> par, cou;
    std::vector<S> weights;
    std::vector<std::tuple<int, int, S>> history;

    explicit undo_dsu(const std::vector<S> &init)
        : par(init.size()), cou(init.size(), 1), weights(init) {
        std::iota(par.begin(), par.end(), 0);
    }
    explicit undo_dsu(int N) : undo_dsu(std::vector<S>(N, S())) {}
    undo_dsu() : undo_dsu(0) {}

    int find(int x) const { return (par[x] == x) ? x : find(par[x]); }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (cou[x] < cou[y]) std::swap(x, y);
        history.emplace_back(y, cou[x], weights[x]);
        return x != y ? par[y] = x, cou[x] += cou[y], weights[x] += weights[y], true : false;
    }

    void set_weight(int x, S w) {
        x = find(x);
        history.emplace_back(x, cou[x], weights[x]);
        weights[x] = w;
    }

    void undo() {
        weights[par[std::get<0>(history.back())]] = std::get<2>(history.back());
        cou[par[std::get<0>(history.back())]] = std::get<1>(history.back());
        par[std::get<0>(history.back())] = std::get<0>(history.back());
        history.pop_back();
    }

    void reset() {
        while (!history.empty()) undo();
    }

    int count(int x) const { return cou[find(x)]; }

    const S &sum(int x) const { return weights[find(x)]; }

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

#line 2 "unionfind/undo_monoid_unionfind.hpp"
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>

// UnionFind, able to rewind to the previous state by undo()
template <class S> struct undo_dsu {
    std::vector<int> par, cou;
    std::vector<S> weights;
    std::vector<std::tuple<int, int, S>> history;

    explicit undo_dsu(const std::vector<S> &init)
        : par(init.size()), cou(init.size(), 1), weights(init) {
        std::iota(par.begin(), par.end(), 0);
    }
    explicit undo_dsu(int N) : undo_dsu(std::vector<S>(N, S())) {}
    undo_dsu() : undo_dsu(0) {}

    int find(int x) const { return (par[x] == x) ? x : find(par[x]); }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (cou[x] < cou[y]) std::swap(x, y);
        history.emplace_back(y, cou[x], weights[x]);
        return x != y ? par[y] = x, cou[x] += cou[y], weights[x] += weights[y], true : false;
    }

    void set_weight(int x, S w) {
        x = find(x);
        history.emplace_back(x, cou[x], weights[x]);
        weights[x] = w;
    }

    void undo() {
        weights[par[std::get<0>(history.back())]] = std::get<2>(history.back());
        cou[par[std::get<0>(history.back())]] = std::get<1>(history.back());
        par[std::get<0>(history.back())] = std::get<0>(history.back());
        history.pop_back();
    }

    void reset() {
        while (!history.empty()) undo();
    }

    int count(int x) const { return cou[find(x)]; }

    const S &sum(int x) const { return weights[find(x)]; }

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

Back to top page