Pagini recente » Cod sursa (job #1350626) | Cod sursa (job #2748009) | Cod sursa (job #1171732) | Cod sursa (job #2556964) | Cod sursa (job #2895697)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100005
void tarjan(int node, vector<int> *G, stack<int> &st, int &index, int *indices, int *lowlink, bool *on_stack, vector<vector<int>> &ans) {
indices[node] = lowlink[node] = ++index;
st.push(node);
on_stack[node] = 1;
for (const int &neigh : G[node])
if (!indices[neigh]) {
tarjan(neigh, G, st, index, indices, lowlink, on_stack, ans);
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);
vector<int> G[NMAX];
for (int i = 1, x, y; i <= m; ++i) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
}
stack<int> st;
int index = 1, indices[NMAX] {}, lowlink[NMAX] {};
bool visited[NMAX] {}, on_stack[NMAX] {};
vector<vector<int>> ans;
for (int i = 1; i <= n; ++i)
if (!indices[i])
tarjan(i, G, st, index, indices, lowlink, on_stack, ans);
printf("%ld\n", ans.size());
for (const vector<int> &v : ans) {
for (const int node : v)
printf("%d ", node);
puts("");
}
}