Strongly Connected Components

Note

• Kosaraju’s Algorithm will give us final SCCs in topological ordering of the condensation graph (the DAG after condensing SCCs into single nodes)

Code (Kosaraju’s Algorithm)

namespace Graph {
    template<int32_t N_> class SCC {
        static_assert(N_ > 0, "N must be positive");
        static constexpr int32_t N = N_;

    private:
        vector<int> in[N], ou[N];
        bool vi[N];
        int n;

        void dfs(int u, vector<int>& p) {
            if (vi[u]) return;
            vi[u] = true;
            for (auto& v : ou[u]) dfs(v, p);
            p.push_back(u);
        }

        void dfs2(int u, vector<int>& co) {
            if (vi[u]) return;
            vi[u] = true;
            co.push_back(u); // place this above or below children dfs as you wish
            for (auto& v : in[u]) dfs2(v, co);
        }

    public:
        SCC() {}

        void set(int n_) { n = n_; for (int i = 1; i <= n; ++i) in[i].clear(), ou[i].clear(); }
        void addEdge(int u, int v) { ou[u].push_back(v); in[v].push_back(u); }

        vector<vector<int>> kosaraju() {
            vector<int> p;
            for (int u = 1; u <= n; ++u) vi[u] = false;
            for (int u = 1; u <= n; ++u) dfs(u, p);
            reverse(p.begin(), p.end());

            vector<vector<int>> scc;
            for (int u = 1; u <= n; ++u) vi[u] = false;
            for (auto& u : p) {
                vector<int> co;
                dfs2(u, co);
                if (!co.empty()) scc.push_back(co);
            }
            return scc;
        }
    };
}

constexpr int N = 1'000'005;
Graph::SCC<N> scc;

inline void solve() {
    int n, m; cin >> n >> m;
    scc.set(n);
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        scc.addEdge(u, v);
    }

    vector<vector<int>> components = scc.kosaraju();
    for (auto& co : components) {
        for (auto& u : co) {
            cout << u << ' ';
        }
        cout << endl;
    }
}