dsu
(Datastructure/top_value_dsu.hpp)

• View this file on GitHub
• Last update: 2024-09-24 04:35:33+09:00
• Include: #include "Datastructure/top_value_dsu.hpp"

概要

ACLのdsuに、いつくかの関数を追加した（実装はACLから取っていない） 参考 : https://github.com/atcoder/ac-library

省略できるもの

edgecnt, componentcnt, groupsは必要が無いなら省略して良いです。

コンストラクタ

dsu d(n)

• 計算量 $O(n)$

関数

• merge(int u, int v)…辺(u, v)を追加する。u, vが非連結だった場合true,そうでなければfalseを返す。
  • 制約 $0 \le u, v < n$
• same(int u, int v)…頂点u, vが連結かどうかを返す。
  • 制約 $0 \le u, v < n$
• leader(int u)…頂点uの属する連結成分の代表元を返す
  • 制約 $0 \le u < n$
• size(int u)…頂点uの属する連結成分のサイズを返す
  • 計算量 $O(1)$
• groups()…グラフを連結成分ごとに分け、その情報を返す
  • 計算量 $O(n)$
  • 備考 groupsで帰ってきた配列のサイズ = 連結成分の個数
• edgecnt(int u) … 頂点uの属する連結成分が持つ辺の本数を返す
  • 計算量 $O(\alpha (n))$
• componentcnt() … {0, … , n-1}について、連結成分の個数を返す
  • 計算量 $O(1)$

verify

edgecnt … https://atcoder.jp/contests/chokudai_S002/submissions/53940535

Code

template<class S, S (*op)(S, S)> struct dsu {
    using vi = vector<int>;   
    using vvi = vector<vector<int>>;
    vi par, sz, es;
    int cc;
    vector<S> dat;

    dsu(const vector<S> d) : dat(d) {
        int n = d.size();
        par = vi(n);
        sz = vi(n, 1);
        es = vi(n, 0);
        cc = n;
        iota(all(par), 0);
    }
  
    int leader(int u) {
        if (par[u] != u) {
            return par[u] = leader(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);

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

    //以下、必要な物を書く

    int size(int u) {
        return sz[leader(u)];
    }

    S value(int u) {
        return dat[leader(u)];
    }
    
    int componentcnt() {
        return cc;
    }
    
    int edgecnt(int u) {
        return es[leader(u)];
    }

    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 dsu
@docs doc/dsu.md
*/

#line 1 "Datastructure/top_value_dsu.hpp"
template<class S, S (*op)(S, S)> struct dsu {
    using vi = vector<int>;   
    using vvi = vector<vector<int>>;
    vi par, sz, es;
    int cc;
    vector<S> dat;

    dsu(const vector<S> d) : dat(d) {
        int n = d.size();
        par = vi(n);
        sz = vi(n, 1);
        es = vi(n, 0);
        cc = n;
        iota(all(par), 0);
    }
  
    int leader(int u) {
        if (par[u] != u) {
            return par[u] = leader(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);

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

    //以下、必要な物を書く

    int size(int u) {
        return sz[leader(u)];
    }

    S value(int u) {
        return dat[leader(u)];
    }
    
    int componentcnt() {
        return cc;
    }
    
    int edgecnt(int u) {
        return es[leader(u)];
    }

    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 dsu
@docs doc/dsu.md
*/

Back to top page