Pagini recente » Cod sursa (job #2229676) | Cod sursa (job #2626226) | Cod sursa (job #57535) | Cod sursa (job #2359540) | Cod sursa (job #497307)
Cod sursa(job #497307)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
int N, M;
vector<vector<int> > G;
vector<vector<int> > C;
stack<int> S;
#define NMAX 100001
int visited[NMAX];
int lowlink[NMAX];
int in_stack[NMAX];
int idx = 0;
void tarjan(int n) {
visited[n] = lowlink[n] = idx; // set the depth index
++idx;
S.push(n); // push on stack
in_stack[n] = 1;
for (int i = 0; i < G[n].size(); ++i) {
int nod = G[n][i];
if (!visited[nod]) tarjan(G[n][i]);
lowlink[n] = min(lowlink[G[n][i]], lowlink[n]);
}
if (lowlink[n] == visited[n]) {
vector<int> aux;
int nod;
do {
nod = S.top(); S.pop();
aux.push_back(nod);
in_stack[nod] = 0;
} while (nod != n);
C.push_back(aux);
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
// reading the graph
scanf("%d %d", &N, &M);
G.resize(N+1);
while (M--) {int x, y; scanf("%d %d", &x, &y); G[x].push_back(y);}
//Tarjan
idx = 1;
for (int i = 1; i <= N; ++i) if (!visited[i]) {
tarjan(i);
}
// done
printf("%d\n", C.size());
for (int i = 0; i < C.size(); ++i) {
for (int j = 0; j < C[i].size(); ++j) {
if (j!=0) printf(" ");
printf("%d", C[i][j]);
}
printf("\n");
}
return 0;
}