tests/yosupo/scc.scc.test.cpp

View this file on GitHub
Last update: 2020-10-29 09:01:05+01:00
Problem: https://judge.yosupo.jp/problem/scc

Depends on

Code

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

#include "../../code/graphs/scc.cc"

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  int n, m;
  cin >> n >> m;

  adj.assign(n, vi());
  F0R(i, m) {
    int u, v;
    cin >> u >> v;
    adj[u].pb(v);
  }

  vvi comp = scc();
  cout << SZ(comp) << endl;
  for(int i = SZ(comp) - 1; ~i; --i) {
      cout << SZ(comp[i]) << ' ';
      for(int x : comp[i])
          cout << x << ' ';
      cout << endl;
  }
}

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

#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/graphs/scc.cc"
vvi adj;
vi dfs_num, dfs_low, S;
vector<bool> onStack;
int dfsCounter;
void scc(int v, vvi& sccs) {
  dfs_num[v] = dfs_low[v] = dfsCounter++;
  S.push_back(v);
  onStack[v] = true;
  for (int u : adj[v]) {
    if (dfs_num[u] == -1) scc(u, sccs);
    if (onStack[u]) ckmin(dfs_low[v], dfs_low[u]);
  }
  if (dfs_num[v] == dfs_low[v]) {
    sccs.eb(); int u;
    do {
      u = S.back();
      S.pop_back();
      onStack[u] = 0;
      sccs.back().pb(u);
    } while (u != v);
  }
}
vvi scc() {
    dfs_num.assign(SZ(adj), -1);
    dfs_low.assign(SZ(adj), 0);
    onStack.assign(SZ(adj), 0);
    dfsCounter = 0;
    vvi sccs;
    F0R (i, SZ(adj))
	if (!~dfs_num[i]) scc(i, sccs);
    return sccs;
}
#line 4 "tests/yosupo/scc.scc.test.cpp"

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  int n, m;
  cin >> n >> m;

  adj.assign(n, vi());
  F0R(i, m) {
    int u, v;
    cin >> u >> v;
    adj[u].pb(v);
  }

  vvi comp = scc();
  cout << SZ(comp) << endl;
  for(int i = SZ(comp) - 1; ~i; --i) {
      cout << SZ(comp[i]) << ' ';
      for(int x : comp[i])
          cout << x << ' ';
      cout << endl;
  }
}