NyaaLIB::GT_SCC

Strongly Connected Components（強連結成分分解）計算量
https://atcoder.github.io/ac-library/production/document_ja/scc.html

• run(void)　有向グラフを強連結成分分解する

戻り値

• g: 強連結成分分解した隣接リスト
• groups: 閉路毎の頂点集合（トポロジカルソート済み）

#include <bits/stdc++.h>

namespace NyaaLIB
{
	template <class E> struct csr
	{
		using ll = long long;
		std::vector<ll> start;
		std::vector<E> elist;
		csr(ll n, const std::vector<std::pair<ll, E>>& edges) : start(n + 1), elist(edges.size())
		{
			for (auto e : edges) start[e.first + 1]++;
			for (ll i = 1; i <= n; i++) start[i] += start[i - 1];
			auto counter = start;
			for (auto e : edges) elist[counter[e.first]++] = e.second;
		}
	};

	// Reference:
	// R. Tarjan,
	// Depth-First Search and Linear Graph Algorithms
	struct GT_SCC
	{	// StronglyConnectedComponents
		using ll = long long;
		GT_SCC(ll n) : _n(n) {}
		GT_SCC(std::vector<std::vector<ll>>& g) : _n(g.size())
		{
			for (ll i = 0; i < (long long)g.size(); i++) for (ll j = 0; j < (long long)g[i].size(); j++) add_edge(i, g[i][j]);
		}
		ll num_vertices() { return _n; }
		void add_edge(ll from, ll to) { edges.push_back({ from, {to} }); }

		// @return pair of (# of scc, scc id)
		std::pair<ll, std::vector<ll>> scc_ids()
		{
			auto g = csr<edge>(_n, edges);
			ll now_ord = 0, group_num = 0;
			std::vector<ll> visited, low(_n), ord(_n, -1), ids(_n);
			visited.reserve(_n);
			auto dfs = [&](auto self, ll v) -> void {
				low[v] = ord[v] = now_ord++;
				visited.push_back(v);
				for (ll i = g.start[v]; i < g.start[v + 1]; i++) {
					auto to = g.elist[i].to;
					if (ord[to] == -1)
					{
						self(self, to);
						low[v] = std::min(low[v], low[to]);
					}
					else low[v] = std::min(low[v], ord[to]);
				}
				if (low[v] == ord[v])
				{
					while (true)
					{
						ll u = visited.back();
						visited.pop_back();
						ord[u] = _n;
						ids[u] = group_num;
						if (u == v) break;
					}
					group_num++;
				}
			};
			for (ll i = 0; i < _n; i++) if (ord[i] == -1) dfs(dfs, i);
			for (auto& x : ids) x = group_num - 1 - x;
			return { group_num, ids };
		}

		struct GT_SCC_RES
		{
			std::vector<std::vector<ll>> g;
			std::vector<std::vector<ll>> groups;
		};

		GT_SCC_RES run()
		{
			GT_SCC_RES res;
			auto ids = scc_ids();
			ll group_num = ids.first;
			std::vector<ll> counts(group_num);
			for (auto x : ids.second) counts[x]++;
			res.groups.resize(ids.first);
			for (ll i = 0; i < group_num; i++) res.groups[i].reserve(counts[i]);
			for (ll i = 0; i < _n; i++) res.groups[ids.second[i]].push_back(i);
			res.g.resize(ids.first);
			for (auto& [from, next] : edges)
			{
				if (ids.second[from] == ids.second[next.to]) continue;
				res.g[ids.second[from]].push_back(ids.second[next.to]);
			}
			return res;
		}

	private:
		ll _n;
		struct edge { ll to; };
		std::vector<std::pair<ll, edge>> edges;
	};
}

実装例
https://atcoder.jp/contests/abc245/submissions/31391423