This documentation is automatically generated by online-judge-tools/verification-helper
#include "icpc/scc.hpp"
#pragma once
#include "icpc/template.hpp"
// https://onlinejudge.u-aizu.ac.jp/problems/2748
V<V<int>> scc(V<V<int>>& g) {
int n = int(g.size());
int now_ord = 0, group_num = 0;
V<int> vis, low(n), ord(n, -1), ids(n);
vis.reserve(n);
auto dfs = [&](auto f, int c) -> void {
low[c] = ord[c] = now_ord++;
vis.push_back(c);
for (auto& e : g[c]) {
if (ord[e] == -1) {
f(f, e);
low[c] = min(low[c], low[e]);
} else {
low[c] = min(low[c], ord[e]);
}
}
if (low[c] == ord[c]) {
while (true) {
int u = vis.back();
vis.pop_back();
ord[u] = n;
ids[u] = group_num;
if (u == c) break;
}
group_num++;
}
};
REP(i, n) if (ord[i] == -1) dfs(dfs, i);
V<V<int>> res(group_num);
REP(i, n) res[group_num - 1 - ids[i]].push_back(i);
return res;
}
#line 2 "icpc/scc.hpp"
#line 2 "icpc/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;
template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
os << "[ ";
for (auto& vi : v) os << vi << ", ";
return os << "]";
}
#ifdef LOCAL
#define show(x) cerr << __LINE__ << " : " << #x << " = " << x << endl;
#else
#define show(x) true
#endif
using uint = unsigned int;
using ull = unsigned long long;
// g++ -g -fsanitize=undefined,address -DLOCAL -std=gnu++17
#line 4 "icpc/scc.hpp"
// https://onlinejudge.u-aizu.ac.jp/problems/2748
V<V<int>> scc(V<V<int>>& g) {
int n = int(g.size());
int now_ord = 0, group_num = 0;
V<int> vis, low(n), ord(n, -1), ids(n);
vis.reserve(n);
auto dfs = [&](auto f, int c) -> void {
low[c] = ord[c] = now_ord++;
vis.push_back(c);
for (auto& e : g[c]) {
if (ord[e] == -1) {
f(f, e);
low[c] = min(low[c], low[e]);
} else {
low[c] = min(low[c], ord[e]);
}
}
if (low[c] == ord[c]) {
while (true) {
int u = vis.back();
vis.pop_back();
ord[u] = n;
ids[u] = group_num;
if (u == c) break;
}
group_num++;
}
};
REP(i, n) if (ord[i] == -1) dfs(dfs, i);
V<V<int>> res(group_num);
REP(i, n) res[group_num - 1 - ids[i]].push_back(i);
return res;
}