Pagini recente » Cod sursa (job #1986573) | Cod sursa (job #2310689) | Cod sursa (job #98440) | Cod sursa (job #197519) | Cod sursa (job #2895704)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100005
vector<int> G[NMAX];
stack<int> st;
int idx = 1, indices[NMAX], lowlink[NMAX];
bool on_stack[NMAX];
vector<vector<int>> ans;
void tarjan(int node) {
indices[node] = lowlink[node] = ++idx;
st.push(node);
on_stack[node] = 1;
for (const int &neigh : G[node])
if (!indices[neigh]) {
tarjan(neigh);
lowlink[node] = min(lowlink[neigh], lowlink[node]);
} else if (on_stack[neigh])
lowlink[node] = min(lowlink[neigh], lowlink[node]);
if (lowlink[node] == indices[node]) {
ans.push_back({});
int curr;
do {
curr = st.top();
st.pop();
on_stack[curr] = 0;
ans.back().push_back(curr);
} while (curr != node);
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1, x, y; i <= m; ++i) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
}
for (int i = 1; i <= n; ++i)
if (!indices[i])
tarjan(i);
printf("%ld\n", ans.size());
for (const vector<int> &v : ans) {
for (const int node : v)
printf("%d ", node);
puts("");
}
}