example/offline_connectivity.example.cpp

• View this file on GitHub
• Last update: 2024-12-28 00:04:13+09:00

Depends on

• offline_connectivity (Datastructure/offline_connectivity.hpp)
• undable dsu (Datastructure/undabledsu.hpp)
• verify用テンプレート (Utility/template.hpp)

Code

#include "../Utility/template.hpp"
#include "../Datastructure/undabledsu.hpp"
#include "../Datastructure/offline_connectivity.hpp"

int main() {
    int n = 10;
    offline_connectivity<dsu, bool, pair<int, int>, false> uf(n); 
    /* 
      n頂点の offlien_connevtivityを宣言。　使用するdsuの型名がdsu 答えの型がbool クエリの型がpair<int, int> 多重辺無し
      この状態では、無辺のグラフ。
    */

    uf.link(0, 1);// 0, 1に辺を貼る。

    uf.query(pair<int, int>(0, 1)); // 0, 1についてクエリを飛ばす

    uf.cut(0, 1); // 0, 1辺を切る

    uf.query(pair<int, int>(0, 1)); // 0, 1についてクエリを飛ばす。


    uf.build(); //クエリを飛ばし終わったら呼ぶ。

    auto f = [&](dsu &UF, pair<int, int> query) {
        return UF.same(query.first, query.second);
    };
    //クエリを処理する関数。 dsuは参照で受け取る。

    vec<bool> res = uf.run(f); //fを引数に渡し、結果を受け取る。

    if(res[0] == true) cout << "0と1は連結だった" << endl;
    if(res[1] == false) cout << "0と1は不連結になった" << endl; 
}

#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/undabledsu.hpp"
struct dsu {
    using vi = vector<int>;   
    using vvi = vec<vi>;
    struct dat {
        int u, v;
        ll x;
        dat(){}
        dat(int a, int b, ll c) : u(a), v(b), x(c) {}
    };
   
    vi par, sz, es;
    vec<ll> val;
    stack<dat> his;
    int cc;
   
    ll op(ll l, ll r) {return l + r;}
    ll inv(ll x) {return -x;}

    dsu(int n) {
        par = vi(n);
        sz = vi(n, 1);
        es = vi(n, 0);
        val = vec<ll>(n, 0);
        cc = n;
        iota(all(par), 0);
    }
  
    int leader(int u) {
        while(par[u] != u) {
            u = par[u];
        }
        return u;
    }
    
    bool same(int a, int b) {
        return leader(a) == leader(b);
    }
    
    bool merge(int a, int b) {
        a = leader(a), b = leader(b);
        if(sz[a] < sz[b]) swap(a, b);
        his.push(dat(a, b, val[a]));

        if(a == b) {
            es[a]++;
            return false;
        }
        else {
            cc--;
            par[b] = a;
            sz[a] += sz[b];
            es[a] += es[b] + 1;
            val[a] = op(val[a] , val[b]);
            return true;
        }
    }

    bool undo() {
        if(his.empty()) return false;
        dat p = his.top();
        auto [u, v, x] = p; 
        his.pop();
        par[v] = v;
        es[u]--;
        if(u != v) {
            cc++;
            sz[u] -= sz[v];
            es[u] -= es[v];
            val[u] = op(val[u], inv( val[v] ));
        }
        return true;
    }

    //以下、必要ないなら省く。

    void set(int v, ll f) {//注意: 代入では無い
        while(1) {
            val[v] = op(val[v], f);
            if(v == par[v]) break;
            v = par[v];
        }
    }

    ll get(int u) {
        return val[leader(u)];
    }

    int size(int u) {//uが含まれる連結成分のサイズを返す
        return sz[leader(u)];
    }

    int edgecnt(int u) {
        return es[leader(u)];
    }

    int component_count() {
        return cc;
    }

    vvi groups() {
        int n = par.size();
        vvi ms(n);
        rep(v, 0, n) {
            ms[leader(v)].push_back(v);
        }

        vvi res;
        rep(i, 0, n) if(ms[i].size() > 0) {
            res.push_back(ms[i]);
        }
        return res;
    }

};

/*
@brief undable dsu
@docs doc/undodsu.md
*/
#line 1 "Datastructure/offline_connectivity.hpp"
template<class dsu, class S, class qif, bool multi_edge>
struct offline_connectivity {
    using pii = pair<int, int>;
    using edge = array<int, 4>;
    using que = pair<int, qif>;
    int n, t, sz, qi, li;
    dsu uf;
    vec<vec<pii>> dat;
    vec<multiset<pii>> es;
    vec<edge> lrs;
    vec<que> qs;
    vec<array<ll, 3>> lz;//{t, 頂点, 作用素}  作用素がllではない場合、頑張る。
    vec<S> res;

    offline_connectivity(int N) : n(N), es(N), qi(0), li(0), t(0), sz(1), uf(N) { }

    void build() {
        rep(u, 0, n) {
            for(auto [v, l] : es[u]) {
                lrs.push_back(edge{l, t, int(u), v});
            }
        }
       
        while(sz < t) sz <<= 1;
        dat.resize(2 * sz);

        for(auto [l, r, u, v] : lrs) {
            l += sz;
            r += sz;
            while(l < r) {
                if(l & 1) dat[l++].emplace_back(u, v);
                if(r & 1) dat[--r].emplace_back(u, v);
                l >>= 1, r >>= 1;
            }
        }
    }

    TT void dfs(T f, int v) {
        for(auto [a, b] : dat[v]) uf.merge(a, b);
        if(v >= sz) {
            while(li < lz.size() && lz[li][0] == v - sz) uf.set(lz[li][1], lz[li][2]), li++;//set→ applyにする必要があるかも(dsuに合わせる)
            if(qi < qs.size() && qs[qi].first == v - sz) res.push_back(f(uf, qs[qi++].second));
        }
        else {
            dfs(f, v * 2);
            dfs(f, v * 2 + 1);
        }
        rep(i, 0, dat[v].size()) uf.undo();
    }
    

    TT vec<S> run(T f) {
        dfs(f, 1);
        return res;
    }

    void link(int u, int v) {
        if(u > v) swap(u, v);
        if(multi_edge == true) es[u].insert(pii(v, t));
        else {
            auto it = es[u].lower_bound(pii(v, -1));
            if(it != es[u].end() && (*it).first == v) return;
            es[u].insert(pii(v, t));
        }
    }

    void cut(int u, int v) {
        if(u > v) swap(u, v);
        auto it = es[u].lower_bound(pii(v, -1));
        if(it == es[u].end()) return;
        auto [tar, l] = *it;
        if(tar != v) return;
        es[u].erase(it);
        lrs.push_back(edge{l, t, u, v});
        
    }

    void query(qif q) {
        qs.push_back(que(t++, q));
    }

    void apply(int v, ll f) {
        lz.push_back({t, v, f});
    }

    void set(int v, ll f) {//ufのapplyに相当する関数名がsetだった時用
        lz.push_back({t, v, f});
    }

};
/*
S f(dsu &uf, qif q) {
    return 答え
}
をrunに渡す
&を付ける事を忘れずに（計算量こわれる）

@brief offline_connectivity
@docs doc/offline_connectivity.md
*/
#line 4 "example/offline_connectivity.example.cpp"

int main() {
    int n = 10;
    offline_connectivity<dsu, bool, pair<int, int>, false> uf(n); 
    /* 
      n頂点の offlien_connevtivityを宣言。　使用するdsuの型名がdsu 答えの型がbool クエリの型がpair<int, int> 多重辺無し
      この状態では、無辺のグラフ。
    */

    uf.link(0, 1);// 0, 1に辺を貼る。

    uf.query(pair<int, int>(0, 1)); // 0, 1についてクエリを飛ばす

    uf.cut(0, 1); // 0, 1辺を切る

    uf.query(pair<int, int>(0, 1)); // 0, 1についてクエリを飛ばす。


    uf.build(); //クエリを飛ばし終わったら呼ぶ。

    auto f = [&](dsu &UF, pair<int, int> query) {
        return UF.same(query.first, query.second);
    };
    //クエリを処理する関数。 dsuは参照で受け取る。

    vec<bool> res = uf.run(f); //fを引数に渡し、結果を受け取る。

    if(res[0] == true) cout << "0と1は連結だった" << endl;
    if(res[1] == false) cout << "0と1は不連結になった" << endl; 
}

Back to top page