Pagini recente » Cod sursa (job #2858023) | Cod sursa (job #2378371) | Cod sursa (job #234555) | Cod sursa (job #1750196) | Cod sursa (job #3297096)
#include <iostream>
#include <vector>
#include <stack>
const int MAXN = 100005;
int n, m;
std::vector<int> adj[MAXN];
std::stack<int> st;
int timestamp;
int finish[MAXN];
int low_link[MAXN];
bool on_stack[MAXN];
std::vector<std::vector<int> > ans;
void rec_tarjan(int node)
{
finish[node] = low_link[node] = timestamp++;
st.push(node);
on_stack[node] = true;
for (int neigh : adj[node]) {
if (finish[neigh] == -1) {
rec_tarjan(neigh);
low_link[node] =
std::min(low_link[node], low_link[neigh]);
} else if (on_stack[neigh]) {
low_link[node] =
std::min(low_link[node], finish[neigh]);
}
}
if (low_link[node] == finish[node]) {
std::vector<int> current_scc;
while (true) {
int node_from_stack = st.top();
st.pop();
on_stack[node_from_stack] = false;
current_scc.push_back(node_from_stack);
if (node_from_stack == node) {
break;
}
}
ans.push_back(current_scc);
}
}
int main(void)
{
#ifndef LOCAL
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
#endif
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
}
for (int i = 1; i <= n; ++i) {
finish[i] = -1;
}
for (int i = 1; i <= n; ++i) {
if (finish[i] == -1) {
rec_tarjan(i);
}
}
std::cout << ans.size() << "\n";
for (const auto &scc : ans) {
for (size_t i = 0; i < scc.size(); ++i) {
std::cout << scc[i] << (i == scc.size() - 1 ? "" : " ");
}
std::cout << "\n";
}
return 0;
}