Pagini recente » Cod sursa (job #75354) | Cod sursa (job #2676264) | Cod sursa (job #477456) | Cod sursa (job #1040311) | Cod sursa (job #1222650)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define MAX 100010
vector<int> Gr[MAX];
stack<int> S;
bool Visited[MAX];
vector<vector<int> > Ctc;
int N, M, Index[MAX], LowLink[MAX], K, Step;
void DFS(int X) {
int Y;
K++;
Index[X] = K;
LowLink[X] = K;
K++;
S.push(X);
Visited[X] = Step;
for (int i = 0; i < Gr[X].size(); i++) {
Y = Gr[X][i];
if (Index[Y] == 0) {
DFS(Y);
LowLink[X] = min(LowLink[X], LowLink[Y]);
} else
if (Visited[Y] == Step) {
LowLink[X] = min(LowLink[X], Index[Y]);
}
}
if (LowLink[X] == Index[X]) {
Ctc.resize(Ctc.size()+1);
do {
Y = S.top();
Ctc[Ctc.size()-1].push_back(Y);
S.pop();
} while (X != Y);
}
}
int main() {
int X, Y;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d", &N, &M);
for (int i = 0; i < M; i++) {
scanf("%d %d", &X, &Y);
Gr[X].push_back(Y);
}
for (int i = 1; i <= N; i++) {
Step++;
if (Index[i] == 0) {
DFS(i);
}
}
printf("%d\n", Ctc.size());
for (int i = 0; i < Ctc.size(); i++) {
for (int j = 0; j < Ctc[i].size(); j++) {
printf("%d ", Ctc[i][j]);
}
printf("\n");
}
return 0;
}