This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ruthen71/rcpl
#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; }