Submit Info #21183

Problem Lang User Status Time Memory
Strongly Connected Components cpp fahimcp495 AC 455 ms 77.77 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
max_random_00 AC 455 ms 77.77 MiB
max_random_01 AC 445 ms 77.70 MiB
max_random_02 AC 453 ms 77.76 MiB
max_random_03 AC 438 ms 77.70 MiB
max_random_04 AC 444 ms 77.76 MiB
random_00 AC 345 ms 61.13 MiB
random_01 AC 367 ms 70.82 MiB
random_02 AC 104 ms 11.92 MiB
random_03 AC 103 ms 51.71 MiB
random_04 AC 120 ms 40.64 MiB

#include<bits/stdc++.h> using namespace std; vector<vector<int>> g, gt, scc; vector<int> vis, order; int sz; void dfs(int& u){ vis[u]=1; for(int& v: g[u]) if(!vis[v]) dfs(v); order.push_back(u); } void dfs2(int& u){ vis[u]=1; scc[sz].push_back(u); for(int& v: gt[u]) if(!vis[v]) dfs2(v); } int main(){ ios::sync_with_stdio(0);cin.tie(0); int n, m; cin >> n >> m; g.resize(n); gt.resize(n); while(m--){ int a, b; cin >> a >> b; g[a].push_back(b); gt[b].push_back(a); } vis.assign(n, 0); for (int i = 0; i < n; ++i){ if(!vis[i]) dfs(i); } vis.assign(n, 0); for (int i = n-1; i >= 0; --i){ int u = order[i]; if(!vis[u]){ scc.emplace_back(0); dfs2(u); sz++; } } cout << sz << "\n"; for (int i = 0; i < sz; ++i){ cout << scc[i].size(); for(int& u: scc[i]){ cout << " " << u; } cout << "\n"; } return 0; }