data_structure/rollback_bipartite_dsu.hpp

• View this file on GitHub
• Last update: 2025-06-07 18:37:17+09:00
• Include: #include "data_structure/rollback_bipartite_dsu.hpp"

Depends on

• data_structure/rollback_dsu.hpp

Code

#pragma once

#include"../data_structure/rollback_dsu.hpp"

namespace noya2 {

struct rollback_bipartite_dsu {
    int n, cc_bipartite;
    rollback_dsu d;
    std::stack<bool> is_rollback;
    rollback_bipartite_dsu (int _n = 0) : n(_n), cc_bipartite(_n), d(_n*2){}
    void inner_merge(int u, int v, int up, int vp){
        if (d.same(u, v)){
            assert(d.same(up, vp));
            is_rollback.push(false);
            return ;
        }
        if (inner_is_bipartite(u) || inner_is_bipartite(v)){
            cc_bipartite--;
            is_rollback.push(true);
        }
        else {
            is_rollback.push(false);
        }
        d.merge(u, v);
        d.merge(up, vp);
        is_rollback.push(true);
    }
    void add_edge(int u, int v, bool w = true){
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        if (w){
            inner_merge(u, n + v, v, n + u);
        }
        else {
            inner_merge(u, v, n + u, n + v);
        }
    }
    bool is_bipartite() const {
        return d.group_count() == cc_bipartite * 2;
    }
    bool is_bipartite(int v){
        assert(0 <= v && v < n);
        return !d.same(v, n + v);
    }
    bool inner_is_bipartite(int v){
        return !d.same(v, (v < n ? n + v : v - n));
    }
    int bipartite_component_count() const {
        return cc_bipartite;
    }
    int non_bipartite_component_count() const {
        return d.group_count() - cc_bipartite * 2;
    }
    int component_count() const {
        return d.group_count() - cc_bipartite;
    }
    void rollback(){
        if (is_rollback.top()){
            is_rollback.pop();
            d.rollback();
            d.rollback();
            if (is_rollback.top()){
                cc_bipartite++;
            }
            is_rollback.pop();
        }
        else {
            is_rollback.pop();
        }
    }
};

} // namespace noya2

#line 2 "data_structure/rollback_bipartite_dsu.hpp"

#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), cc(_n), par_or_siz(_n,-1) {}
    int leader(int v) const {
        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) const {
        return leader(u) == leader(v);
    }
    int merge(int u, int v){
        u = leader(u);
        v = leader(v);
        logs.emplace(u, par_or_siz[u]);
        logs.emplace(v, par_or_siz[v]);
        logs.emplace(cc, 0);
        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;
        cc--;
        return u;
    }
    int size(int v) const {
        return -par_or_siz[leader(v)];
    }
    int group_count() const {
        return cc;
    }
    void rollback(){
        cc = logs.top().first; logs.pop();
        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, cc;
    std::vector<int> par_or_siz;
    std::stack<std::pair<int,int>> logs;
};

} // namespace noya2
#line 4 "data_structure/rollback_bipartite_dsu.hpp"

namespace noya2 {

struct rollback_bipartite_dsu {
    int n, cc_bipartite;
    rollback_dsu d;
    std::stack<bool> is_rollback;
    rollback_bipartite_dsu (int _n = 0) : n(_n), cc_bipartite(_n), d(_n*2){}
    void inner_merge(int u, int v, int up, int vp){
        if (d.same(u, v)){
            assert(d.same(up, vp));
            is_rollback.push(false);
            return ;
        }
        if (inner_is_bipartite(u) || inner_is_bipartite(v)){
            cc_bipartite--;
            is_rollback.push(true);
        }
        else {
            is_rollback.push(false);
        }
        d.merge(u, v);
        d.merge(up, vp);
        is_rollback.push(true);
    }
    void add_edge(int u, int v, bool w = true){
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        if (w){
            inner_merge(u, n + v, v, n + u);
        }
        else {
            inner_merge(u, v, n + u, n + v);
        }
    }
    bool is_bipartite() const {
        return d.group_count() == cc_bipartite * 2;
    }
    bool is_bipartite(int v){
        assert(0 <= v && v < n);
        return !d.same(v, n + v);
    }
    bool inner_is_bipartite(int v){
        return !d.same(v, (v < n ? n + v : v - n));
    }
    int bipartite_component_count() const {
        return cc_bipartite;
    }
    int non_bipartite_component_count() const {
        return d.group_count() - cc_bipartite * 2;
    }
    int component_count() const {
        return d.group_count() - cc_bipartite;
    }
    void rollback(){
        if (is_rollback.top()){
            is_rollback.pop();
            d.rollback();
            d.rollback();
            if (is_rollback.top()){
                cc_bipartite++;
            }
            is_rollback.pop();
        }
        else {
            is_rollback.pop();
        }
    }
};

} // namespace noya2

Back to top page