test/graph/scc.test.cpp

View this file on GitHub
Last update: 2025-10-17 22:12:07+08:00
Problem: https://judge.yosupo.jp/problem/scc

Depends on

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/scc
#include <bits/stdc++.h>
#define PUSHB push_back
using namespace std;
using pii = pair<int, int>;
using ll = long long;

#include "../../src/graph/scc.hpp"
#include "../../src/misc/read.hpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read(), m = read();
  vector<pii> E(m);
  SCC scc(n);
  for (auto& [u, v] : E) {
    u = read(), v = read();
    scc.adde(u, v);
  }
  int N = scc.work();
  vector<int> indeg(N);
  vector<vector<int>> H(N), sccvtx(N);
  for (int i = 0; i < n; i++) sccvtx[scc.sccid[i]].PUSHB(i);
  for (const auto& [u, v] : E) {
    int su = scc.sccid[u], sv = scc.sccid[v];
    if (su != sv) {
      H[su].PUSHB(sv);
      indeg[sv]++;
    }
  }

  queue<int> que;
  for (int i = 0; i < N; i++) {
    if (indeg[i] == 0) que.push(i);
  }

  vector<int> ans;
  ans.reserve(N);
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    ans.PUSHB(u);
    for (int v : H[u]) {
      if (--indeg[v] == 0) {
        que.push(v);
      }
    }
  }

  cout << N << "\n";
  for (int i : ans) {
    cout << sccvtx[i].size();
    for (int v : sccvtx[i]) cout << " " << v;
    cout << "\n";
  }
  return 0;
}

#line 1 "test/graph/scc.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/scc
#include <bits/stdc++.h>
#define PUSHB push_back
using namespace std;
using pii = pair<int, int>;
using ll = long long;

#line 1 "src/graph/scc.hpp"
// 有向图的强连通分量. 返回强联通分量个数, 点对应的强连通分量编号在 `sccid` 中.
struct SCC {
  int n, cur_dfn, cur_scc;
  stack<int> stk;
  vector<int> dfn, low, sccid;
  vector<vector<int>> G;
  SCC(int n) : n(n), dfn(n, -1), low(n), sccid(n, -1), G(n) {}
  void adde(int u, int v) { G[u].PUSHB(v); }
  int work() {
    cur_dfn = cur_scc = 0;
    for (int i = 0; i < n; i++)
      if (dfn[i] == -1) tarjan(i);
    assert(stk.empty());
    return cur_scc;
  }

 private:
  void tarjan(int u) {
    dfn[u] = low[u] = cur_dfn++, stk.push(u);
    for (int v : G[u]) {
      if (dfn[v] == -1) {
        tarjan(v), low[u] = min(low[u], low[v]);
      } else if (sccid[v] == -1) {
        low[u] = min(low[u], dfn[v]);
      }
    }
    if (dfn[u] == low[u]) {
      int v;
      do {
        v = stk.top(), stk.pop(), sccid[v] = cur_scc;
      } while (v != u);
      cur_scc++;
    }
  }
};
#line 1 "src/misc/read.hpp"
#define GC ch = getchar_unlocked()
ll read() {
  ll x = 0, f = 1, GC;
  while (ch < '0' || ch > '9') ch == '-' ? f = -1, GC : GC;
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', GC;
  return x * f;
}
#undef GC
#line 10 "test/graph/scc.test.cpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read(), m = read();
  vector<pii> E(m);
  SCC scc(n);
  for (auto& [u, v] : E) {
    u = read(), v = read();
    scc.adde(u, v);
  }
  int N = scc.work();
  vector<int> indeg(N);
  vector<vector<int>> H(N), sccvtx(N);
  for (int i = 0; i < n; i++) sccvtx[scc.sccid[i]].PUSHB(i);
  for (const auto& [u, v] : E) {
    int su = scc.sccid[u], sv = scc.sccid[v];
    if (su != sv) {
      H[su].PUSHB(sv);
      indeg[sv]++;
    }
  }

  queue<int> que;
  for (int i = 0; i < N; i++) {
    if (indeg[i] == 0) que.push(i);
  }

  vector<int> ans;
  ans.reserve(N);
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    ans.PUSHB(u);
    for (int v : H[u]) {
      if (--indeg[v] == 0) {
        que.push(v);
      }
    }
  }

  cout << N << "\n";
  for (int i : ans) {
    cout << sccvtx[i].size();
    for (int v : sccvtx[i]) cout << " " << v;
    cout << "\n";
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	6 ms	4 MB
g++	large_cycle_00	AC	123 ms	64 MB
g++	max_random_00	AC	325 ms	88 MB
g++	max_random_01	AC	357 ms	88 MB
g++	max_random_02	AC	306 ms	88 MB
g++	max_random_03	AC	355 ms	88 MB
g++	max_random_04	AC	355 ms	88 MB
g++	random_00	AC	243 ms	70 MB
g++	random_01	AC	308 ms	81 MB
g++	random_02	AC	42 ms	15 MB
g++	random_03	AC	108 ms	59 MB
g++	random_04	AC	97 ms	44 MB