data_structure/rollback_dsu.hpp

• View this file on GitHub
• Last update: 2024-07-28 13:57:54+09:00
• Include: #include "data_structure/rollback_dsu.hpp"

Required by

• data_structure/offline_dynamic_connectivity.hpp

Verified with

• test/data_structure/aoj_2235.test.cpp

Code

#pragma once

#include <vector>
#include <stack>
#include <utility>
#include <cassert>

namespace noya2 {

struct rollback_dsu {
    rollback_dsu (int _n = 0) : n(_n), par_or_siz(_n,-1) {}
    int leader(int v){
        assert(0 <= v && v < n);
        if (par_or_siz[v] < 0) return v;
        return leader(par_or_siz[v]);
    }
    bool same(int u, int v){
        return leader(u) == leader(v);
    }
    int merge(int u, int v){
        u = leader(u);
        v = leader(v);
        logs.push(make_pair(u,par_or_siz[u]));
        logs.push(make_pair(v,par_or_siz[v]));
        if (u == v) return u;
        if (-par_or_siz[u] < -par_or_siz[v]) std::swap(u,v);
        par_or_siz[u] += par_or_siz[v];
        par_or_siz[v] = u;
        return u;
    }
    int size(int v){
        return -par_or_siz[leader(v)];
    }
    void rollback(){
        par_or_siz[logs.top().first] = logs.top().second; logs.pop();
        par_or_siz[logs.top().first] = logs.top().second; logs.pop();
    }
  private:
    int n;
    std::vector<int> par_or_siz;
    std::stack<std::pair<int,int>> logs;
};

} // namespace noya2

#line 2 "data_structure/rollback_dsu.hpp"

#include <vector>
#include <stack>
#include <utility>
#include <cassert>

namespace noya2 {

struct rollback_dsu {
    rollback_dsu (int _n = 0) : n(_n), par_or_siz(_n,-1) {}
    int leader(int v){
        assert(0 <= v && v < n);
        if (par_or_siz[v] < 0) return v;
        return leader(par_or_siz[v]);
    }
    bool same(int u, int v){
        return leader(u) == leader(v);
    }
    int merge(int u, int v){
        u = leader(u);
        v = leader(v);
        logs.push(make_pair(u,par_or_siz[u]));
        logs.push(make_pair(v,par_or_siz[v]));
        if (u == v) return u;
        if (-par_or_siz[u] < -par_or_siz[v]) std::swap(u,v);
        par_or_siz[u] += par_or_siz[v];
        par_or_siz[v] = u;
        return u;
    }
    int size(int v){
        return -par_or_siz[leader(v)];
    }
    void rollback(){
        par_or_siz[logs.top().first] = logs.top().second; logs.pop();
        par_or_siz[logs.top().first] = logs.top().second; logs.pop();
    }
  private:
    int n;
    std::vector<int> par_or_siz;
    std::stack<std::pair<int,int>> logs;
};

} // namespace noya2

Back to top page