強連結成分分解の実装(C++)

1. 概要

1-1. 趣旨

強連結成分分解とは？という話は色々なサイトに書かれているが、実装して、コードを1行ずつ解説してくれる記事がなかった。自分の理解を兼ねて、コードに1行ずつ解説を付けたものを貼る。

1-2. 概念自体の解説記事

こちらが非常にわかりやすく感じた。
https://mathtrain.jp/kyorenketsu

1-3. 使用した問題

Aizu Online Judge GRL-3C
https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_C

2. 実装

C++17で実装。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll //int:2*10**9
typedef long double ld;
typedef pair<ll,ll> P;
#define REP(i,n) for(ll i = 0; i<(ll)(n); i++)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define pb push_back
#define MOD 1000000007 //998244353
#define PI 3.141592653
#define INF 100000000000000 //14
//cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
#define N 11000

vector<vector<pair<ll,bool>>> conn(N);
vector<ll> checked(N,0); // dfs参照
vector<ll> orderList(N,-1); // dfsで通った順番に登録していく
vector<ll> groupList(N,-1); // 各nodeにgroupをつけていく
ll cnt = 0;

void dfs(ll now, ll prev) { 
    // 帰り道に通った順に番号をつける, 重複が起きないように行きにcheckedする
    // orderList[i]はi番のnode
    checked[now]=1;
    for (auto v : conn[now]) {
        // すでに見たところ、親、false(逆向きの枝)
        if (checked[v.first]==1 || v.first==prev || v.second==false) continue;
        dfs(v.first,now);
    }
    // 通った順に番号をつける
    orderList[cnt]=now; cnt++;
    return;
}


void dfs2(ll now, ll group) {
    // nowが今見るnode, groupが登録するgroup番号
    groupList[now]=group;
    for (auto v : conn[now]) {
        // すでにgroup番号が付いてるnode、逆向きでない枝はスルー
        if (groupList[v.first]!=-1 || v.second==true) continue;
        // nowから行けるところに、同じgroup番号をつける
        dfs2(v.first,group);
    }
    return;
}

int main(){
    ll n, m; cin >> n >> m;
    REP(i,m) {
        ll u, v; cin >> u >> v;
        // trueで登録するのは元の向きの枝
        // falseは逆向きの枝(dfs2で用いる)
        conn[u].pb({v,true});
        conn[v].pb({u,false});
    }
    REP(i,n) if (!checked[i]) {
        // 連結グラフでない場合には開始点が複数個必要
        dfs(i,-1);
    }
    FORD(i,n-1,0) {
        // -1のときはそれ以降も全部-1なのでbreak
        // 単独のnodeがある場合は、orderListにn個全部が登録されないので、あまりの枠が出る
        if (orderList[i]==-1) break;
        // すでに見たnodeの場合はgroupListにgroup番号が登録されているので、スルー
        if (groupList[orderList[i]]!=-1) continue;
        // 始点となるnodeの番号をグループ番号とする
        dfs2(orderList[i],orderList[i]);
    }
    ll q; cin >> q;
    REP(i,q) {
        ll u, v; cin >> u >> v;
        // 同じグループに属する場合は1, そうでなければ0
        if (groupList[u]==groupList[v]) cout << 1 << endl;
        else cout << 0 << endl;
    }
    return 0;
}

3. クラス化しておく

struct SCC {
    ll n;
    vector<vector<pair<ll,bool>>> conn;
    vector<ll> checked;
    vector<ll> orderList;
    vector<ll> groupList;
    ll cnt = 0;
    SCC(ll n) : n(n), conn(n), checked(n,0), orderList(n,-1), groupList(n,-1) {};
    void dfs(ll now, ll prev) {
        checked[now]=1;
        for (auto v : conn[now]) {
            if (checked[v.first]==1 || v.first==prev || v.second==false) continue;
            dfs(v.first,now);
        }
        orderList[cnt]=now; cnt++;
        return;
    }
    void dfs2(ll now, ll group) {
        groupList[now]=group;
        for (auto v : conn[now]) {
            if (groupList[v.first]!=-1 || v.second==true) continue;
            dfs2(v.first,group);
        }
        return;
    }
    void make_group() {
        REP(i,n) if (!checked[i]) dfs(i,-1);
        FORD(i,n-1,0) {
            if (orderList[i]==-1) break;
            if (groupList[orderList[i]]!=-1) continue;
            dfs2(orderList[i],orderList[i]);
        }
    }
};

4. 終わりに

アルゴリズムの解説記事が多い割には、実装まで面倒見よく解説してくれる記事ってあまりなくて、もっとあったら嬉しいなとよく思ってたので、今回勉強ついでに書いてみた。（意外にこういうのって需要あると思うんですが、どうなのでしょうか。)

ここをこう書いたほうがスマートじゃないか？などの指摘があれば是非コメントなど頂けると幸いです。