test/strongly_connected_components.test.cpp

• View this file on GitHub
• Last update: 2022-08-27 12:40:11+09:00
• Problem: https://judge.yosupo.jp/problem/scc

Depends on

• graph/strongly_connected_components.cpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#include <bits/stdc++.h>
using namespace std;
#include "../graph/strongly_connected_components.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    StronglyConnectedComponents scc(n);
    int a, b;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        scc.add_edge(a, b);
    }
    scc.build(false);

    cout << scc.N_scc << '\n';
    for (int i = 0; i < scc.N_scc; i++) {
        cout << (int)(scc.scc_group[i].size()) << ' ';
        for (int &u : scc.scc_group[i]) {
            cout << u << " ";
        }
        cout << '\n';
    }
    return 0;
}

#line 1 "test/strongly_connected_components.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#include <bits/stdc++.h>
using namespace std;
#line 3 "graph/strongly_connected_components.cpp"
using namespace std;

struct StronglyConnectedComponents {
  private:
    std::vector<int> visited;
    std::vector<int> memo;

    void _dfs(int v) {
        group[v] = -1;
        for (const int &u : G[v]) {
            if (group[u] > 0) _dfs(u);
        }
        order.push_back(v);
    }

    void rdfs(int v, int cnt) {
        group[v] = cnt;
        scc_group[cnt].push_back(v);
        for (const int &u : rG[v]) {
            if (group[u] < 0) rdfs(u, cnt);
        }
    }

    int _dp(int v) {
        if (visited[v] >= 0) return memo[v];
        int ret = 0;
        for (const int &u : sccG[v]) {
            ret |= _dp(u);
        }
        visited[v]     = 1;
        return memo[v] = ret;
    }

  public:
    int N, N_scc;
    std::vector<std::vector<int>> G, rG;
    std::vector<int> group, order;
    std::vector<std::vector<int>> scc_group, sccG;

    // StronglyConnectedComponents receives N as the number of vertex of graph G.
    StronglyConnectedComponents(int N) : N(N) {
        G.resize(N);
        rG.resize(N);
        group.assign(N, 1);
    }

    // add_edge receives a,b and creates edge a -> b.
    // contraint: 0 <= a,b < N
    void add_edge(int a, int b) {
        G[a].push_back(b);
        rG[b].push_back(a);
    }

    // build bulids strongly connected components.
    // when build_scc is true, build scc_G
    void build(bool build_scc) {
        for (int i = 0; i < N; i++) {
            if (group[i] > 0) _dfs(i);
        }
        std::reverse(order.begin(), order.end());
        N_scc = 0;
        for (const int &v : order) {
            if (group[v] < 0) {
                scc_group.push_back({});
                rdfs(v, N_scc);
                N_scc++;
            }
        }

        if (!build_scc)
            return;

        sccG.resize(N_scc);
        for (int i = 0; i < N_scc; i++) {
            std::set<int> st;
            for (const int &v : scc_group[i]) {
                for (const int &u : G[v]) {
                    st.insert(group[u]);
                }
            }
            for (auto itr = st.begin(); itr != st.end(); itr++) {
                sccG[i].push_back(*itr);
            }
        }
    }

    // DP MUST BE IMPLEMENTED DEPENDING ON THE PROBLEM TO BE SOLVED.
    // build must be called before dp is called.
    int dp() {
        visited.assign(N_scc, -1);
        memo.resize(N_scc, 0);
        for (int i = 0; i < N_scc; i++) {
            if ((int)scc_group[i].size() > 1) {
                memo[i]    = 1;
                visited[i] = 1;
            }
        }

        int ans = 0;
        for (int i = 0; i < N_scc; i++) {
            if (_dp(i)) ans += (int)scc_group[i].size();
        }
        return ans;
    }

    // scc[i] returns a group which vertex i belongs to.
    // this function is valid after build () is called.
    int operator[](int i) {
        return group[i];
    }
};
#line 5 "test/strongly_connected_components.test.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    StronglyConnectedComponents scc(n);
    int a, b;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        scc.add_edge(a, b);
    }
    scc.build(false);

    cout << scc.N_scc << '\n';
    for (int i = 0; i < scc.N_scc; i++) {
        cout << (int)(scc.scc_group[i].size()) << ' ';
        for (int &u : scc.scc_group[i]) {
            cout << u << " ";
        }
        cout << '\n';
    }
    return 0;
}

Back to top page