Pagini recente » Cod sursa (job #1988875) | Cod sursa (job #3291200) | Cod sursa (job #2985658) | Cod sursa (job #2985641) | Cod sursa (job #1494177)
#include <stdio.h>
#include <vector>
#include <stack>
#define maxdim 100005
using namespace std;
int n, m, p;
int lowest[maxdim], ind[maxdim], inSt[maxdim];
vector<int> G[maxdim];
vector<vector<int>> sol;
stack<int> st;
void dfs(int nod) {
lowest[nod] = ind[nod] = ++p;
st.push(nod); inSt[nod] = 1;
for (int son : G[nod]) {
if (!lowest[son]) {
dfs(son);
lowest[nod] = min(lowest[nod], lowest[son]);
} else {
if (inSt[son]) {
lowest[nod] = min(lowest[nod], ind[son]);
}
}
}
if (lowest[nod] == ind[nod]) {
vector<int> crt; int x;
do {
x = st.top(); st.pop(); inSt[x] = 0;
crt.push_back(x);
} while (nod != x);
sol.push_back(crt);
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) {
int x, y; scanf("%d %d", &x, &y);
G[x].push_back(y);
}
for (int i = 1; i <= n; ++i) {
if (!lowest[i]) {
dfs(i);
}
}
printf("%d\n", (int) sol.size());
for (vector<int> &crt : sol) {
for (int nod : crt) {
printf("%d ", nod);
}
printf("\n");
}
return 0;
}