< hamamuさんのAI生成コード置き場

二重辺連結成分分解

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

//generated by GPT-5.4, modified by hamamu
template<class E> struct TwoEdgeConnectedComponents{
    using ll = long long;
    using Int = long long;
    vector<vector<E>> &to; //元のグラフ
    ll n; //頂点数
    vector<ll> ord; //ord[v]:DFSで頂点vを最初に訪れた順番
    vector<ll> low; //low[v]:v以下のDFS木から、後退辺を1本まで使って到達できる最小ord
    ll ordcnt = 1;  //ordの採番カウンタ
    vector<pair<ll,ll>> bridges; //橋の一覧
    vector<ll> ccids;       //ccids[v]:頂点vが属する二重辺連結成分ID
    vector<vector<ll>> cc;  //cc[id]:成分idに属する頂点列
    vector<vector<E>> tocc; //成分縮約後の木(森)
    unordered_map<ll,pair<ll,ll>> bridgeByCc; //成分番号ペア→元の橋の両端頂点

    // グラフを受け取り、以下をまとめて構築する。
    // 1. 橋検出
    // 2. 二重辺連結成分分解
    // 3. 成分木の構築
    TwoEdgeConnectedComponents(vector<vector<E>> &to)
        : to(to),n((ll)to.size()),ord(n),low(n),ccids(n,-1)
    {
        // ---- 橋検出 ----
        for (ll v = 0; v <= n - 1; ++v){
            if (ord[v] != 0) continue;
            dfsBridge(v);
        }

        // ---- 二重辺連結成分抽出 ----
        ll ccnm = 0;
        for (ll v = 0; v <= n - 1; ++v){
            if (ccids[v] != -1) continue;
            ccids[v] = ccnm++;
            dfsCc(v);
        }
        // 各成分に属する頂点を集約する
        cc.resize(ccnm);
        for (ll v = 0; v <= n - 1; ++v){
            cc[ccids[v]].push_back(v);
        }

        // ---- 成分木の構築 ----
        // 橋だけが成分間を結ぶので、bridges からそのまま作れる
        tocc.resize(ccnm);
        bridgeByCc.reserve(bridges.size());
        for (auto[v,u]: bridges){
            ll vv = ccids[v];
            ll uu = ccids[u];
            tocc[vv].emplace_back(uu);
            tocc[uu].emplace_back(vv);
            if (vv > uu) swap(vv,uu), swap(v,u); //キーの向きを統一
            bridgeByCc[keyCc(vv,uu)] = {v,u}; //辺vv-uuに対応する元の橋を保存
        }
    }

    pair<ll,ll> bridgeEndsCc(ll vv,ll uu) const{
        bool rev = false;
        if (vv > uu) swap(vv,uu), rev = true; //検索用に成分番号の順序を正規化
        auto it = bridgeByCc.find(keyCc(vv,uu));
        assert(it != bridgeByCc.end());
        auto [v,u] = it->second;
        if (rev) swap(v,u); //v,uの順序を、呼び出し時のvv,uuの順序と合わせる
        return {v,u};
    }

private:
    //成分番号の組をunordered_map用の1つの整数キーに変換
    ll keyCc(ll vv,ll uu) const{
        return vv * n + uu;
    }

    // DFSで橋を検出する
    void dfsBridge(ll v,ll p = -1){
        ord[v] = low[v] = ordcnt++;
        bool beet = false;
        for (ll u : to[v]){
            //親への辺は1本だけ無視し、多重辺は後退辺として扱う
            if (u == p && !exchange(beet,true)) continue;

            // 訪問済みなら後退辺
            if (ord[u] != 0){
                low[v] = min(low[v],ord[u]);
                continue;
            }

            // 未訪問なら木辺として DFS
            dfsBridge(u,v);

            // 子側から low を持ち上げる
            low[v] = min(low[v],low[u]);

            // v-u が橋なら記録する
            if (isBridge(v,u)) bridges.emplace_back(v,u);
        }
    }

    // 辺v-u が橋かどうかを判定する
    // ordが小さい方を親側とみなして判定している
    bool isBridge(ll v,ll u){
        if (ord[v] > ord[u]) swap(v,u);
        return ord[v] < low[u];
    }

    // 橋をまたがないようにDFSして、同じ二重辺連結成分を塗る
    void dfsCc(ll v){
        for (ll u : to[v]){
            if (ccids[u] != -1) continue;
            if (isBridge(v,u)) continue;

            ccids[u] = ccids[v];
            dfsCc(u);
        }
    }
};
/*
- ---- 準備 ----
TwoEdgeConnectedComponents te(to);
- ---- 使用 ----
vpll &brs=te.bridges;  //橋の一覧  例{(3,4),(9,12),(13,9),…}
ll     vv=te.ccids[v]; //頂点vの成分番号
vll   &vs=te.cc[vv];   //成分番号vvに属する頂点集合
bool isBr=te.isBridge(v,u); //true:辺vuが橋
auto[v,u]=te.bridgeEndsCc(vv,uu); //成分vv-uuを結ぶ橋の両端頂点  vはvv側、uはuu側
auto &tocc=te.tocc; //成分を頂点とするグラフ(必ず木/森)
*/