Pagini recente » Cod sursa (job #525421) | Cod sursa (job #1672291) | Cod sursa (job #426032) | Cod sursa (job #1695137) | Cod sursa (job #3124233)
#include <bits/stdc++.h>
using namespace std;
void dfs(int node, vector<int> &discovery, vector<bool> &in_stack, vector<int> &lowest, stack<int> &s, vector<vector<int>> &adj, vector<vector<int>> &ctcs, int &t) {
discovery[node] = ++t;
lowest[node] = discovery[node];
s.push(node);
in_stack[node] = true;
for (int neigh : adj[node]) {
if (discovery[neigh] && !in_stack[neigh])
continue;
if (!discovery[neigh])
dfs(neigh, discovery, in_stack, lowest, s, adj, ctcs, t);
lowest[node] = min(lowest[node], lowest[neigh]);
}
if (lowest[node] == discovery[node]) {
ctcs.push_back(vector<int> {});
int x;
do {
x = s.top();
ctcs.back().push_back(x);
s.pop();
in_stack[x] = false;
} while (x != node);
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(1 + n, vector<int> ()), ctcs;
for (int edge = 1, a, b; edge <= m; ++edge) {
cin >> a >> b;
adj[a].push_back(b);
}
stack <int> s;
vector<int> discovery(1 + n, 0), lowest(1 + n);
vector<bool> in_stack(1 + n, false);
for (int i = 1, t = 0; i <= n; ++i)
if (!discovery[i])
dfs(i, discovery, in_stack, lowest, s, adj, ctcs, t);
cout << ctcs.size() << '\n';
for (auto ctc : ctcs) {
for (int x : ctc)
cout << x << ' ';
cout << '\n';
}
return 0;
}