graph/test/Strongly_Connected_Components.test.cpp

• View this file on GitHub
• Last update: 2023-07-25 00:50:50+07:00
• Problem: https://judge.yosupo.jp/problem/scc

Depends on

• Strongly Connected Component (graph/scc.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/scc"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#include "../scc.hpp"

void solve(int ith) {
  int n, m;
  cin >> n >> m;
  scc g(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    g.add_edge(u, v);
  }
  g.build();
  auto comp = g.scc_list;
  cout << comp.size() << '\n';
  for (auto c : comp) {
    cout << c.size() << ' ';
    for (auto v : c) cout << v << ' ';
    cout << '\n';
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cin.exceptions(cin.failbit);
  int tc = 1;
  // cin >> tc;
  for (int i = 1; i <= tc; ++i) solve(i);
}

#line 1 "graph/test/Strongly_Connected_Components.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/scc"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#line 2 "graph/scc.hpp"

struct scc {
  vector<vector<int>> g;
  int n;
  vector<int> num, low, current, S;
  int counter;
  vector<int> id;
  vector<vector<int>> scc_list;

  scc(int n)
      : g(n),
        n(n),
        num(n, -1),
        low(n, 0),
        current(n, 0),
        counter(0),
        id(n, -1) {}

  void add_edge(int u, int v) { g[u].push_back(v); }

  void dfs(int u) {
    low[u] = num[u] = counter++;
    S.push_back(u);
    current[u] = 1;
    for (auto v : g[u]) {
      if (num[v] == -1) dfs(v);
      if (current[v]) low[u] = min(low[u], low[v]);
    }
    if (low[u] == num[u]) {
      scc_list.push_back(vector<int>());
      while (1) {
        int v = S.back();
        S.pop_back();
        current[v] = 0;
        scc_list.back().push_back(v);
        id[v] = (int)scc_list.size() - 1;
        if (u == v) break;
      }
    }
  }

  // build scc_list
  void build() {
    for (int i = 0; i < n; i++) {
      if (num[i] == -1) dfs(i);
    }
    reverse(begin(scc_list), end(scc_list));
  }

  // build DAG of strongly connected components
  // Returns: adjacency list of DAG, and root vertices (in-degree
  // = 0)
  pair<vector<vector<int>>, vector<int>> condense() {
    vector<vector<int>> dag(scc_list.size());
    vector<int> roots, in(scc_list.size());
    for (int u = 0; u < n; ++u) {
      int x = id[u];
      for (int v : g[u]) {
        int y = id[v];
        if (x != y) {
          dag[x].push_back(y);
          ++in[y];
        }
      }
    }
    for (int u = 0; u < (int)dag.size(); ++u)
      if (in[u] == 0) roots.push_back(u);
    return {dag, roots};
  }
};
#line 10 "graph/test/Strongly_Connected_Components.test.cpp"

void solve(int ith) {
  int n, m;
  cin >> n >> m;
  scc g(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    g.add_edge(u, v);
  }
  g.build();
  auto comp = g.scc_list;
  cout << comp.size() << '\n';
  for (auto c : comp) {
    cout << c.size() << ' ';
    for (auto v : c) cout << v << ' ';
    cout << '\n';
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cin.exceptions(cin.failbit);
  int tc = 1;
  // cin >> tc;
  for (int i = 1; i <= tc; ++i) solve(i);
}

Back to top page