【典型90問】021 - Come Back in One Piece（★5）

atcoder.jp

強連結成分分解を初めて学んだので、メモしておくために記事にします。
アルゴリズムの正当性とかはまだちゃんと分かっていない気がするので、役に立ったリソースだけまとめておきます。

• 高校数学の美しい物語ってグラフ理論の解説とかもしているんですね。

manabitimes.jp

• スライドでわかりやすい。スライドってそのまま引用先に埋め込めちゃうんですね。

目指せグラフマスター from HCPC: 北海道大学競技プログラミングサークル

www.slideshare.net

• こちらもスライド。アルゴリズムをトレースする様子がわかりやすい。

https://hcpc-hokudai.github.io/archive/graph_scc_001.pdf

• 絵がわかりやすい。

scrapbox.io

解法

強連結成分分解したらそれぞれの成分で $ {}_n C_2 $ を求めて、合計すれば答え。

実装

あまり綺麗に実装できなかった。人の実装を見て勉強したいと思います。

int num = 1;
void dfs1(int n, vector<vint> &G, vector<int> &cnt, vector<int> &seen) {
    seen[n] = 1; 

    for (auto t : G[n]) if (!seen[t]) dfs1(t, G, cnt, seen);

    cnt[n] = num;
    num++;
}

void dfs2(int n, vector<vint> &G, vector<int> &seen, vector<int> &v) {
    seen[n] = 1;
    v.push_back(n);
    
    for (auto t : G[n]) if (!seen[t]) dfs2(t, G, seen, v);
}

void solve(long long N, long long M, std::vector<long long> A, std::vector<long long> B) {
    // GR: 逆辺にしたグラフ
    vector<vector<long long>> G(N), GR(N);
    for (int i = 0; i < M; i++) {
        G[A[i]-1].push_back(B[i]-1);
        GR[B[i]-1].push_back(A[i]-1);

    }
    
    // 一回目のDFS
    vector<int> cnt(N), seen(N, 0);
    REP (i, N) {
        if (seen[i]) continue;

        dfs1(i, G, cnt, seen);
    }

    // 大きい順にソート
    vector<pair<int, int>> vec;
    REP (i, N) vec.push_back({cnt[i], i});
    sort(rall(vec));

    // 2回目のDFS
    seen.assign(N, 0);
    vector<vector<int>> dec;
    REP (i, N) {
        if (seen[vec[i].second]) continue;

        vector<int> v;
        dfs2(vec[i].second, GR, seen, v);
        dec.push_back(v);
    }

    // 答えを集計
    ll ans = 0;
    REP (i, dec.size()) ans += dec[i].size() * (dec[i].size()-1) / 2;
    
    c(ans) // 出力
}