Pagini recente » Cod sursa (job #1640660) | Cod sursa (job #2334608) | Cod sursa (job #2112290) | Cod sursa (job #1335657) | Cod sursa (job #1222629)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 100010
vector<int> Gr[MAX], Tr[MAX];
vector<vector<int> > Ctc;
int N, M, GrViz[MAX], TrViz[MAX], K = 1;
void GrDfs(int X) {
GrViz[X] = K;
for (int i = 0; i < Gr[X].size(); i++) {
if (GrViz[Gr[X][i]] < K) {
GrDfs(Gr[X][i]);
}
}
}
void TrDfs(int X) {
TrViz[X] = K;
if (GrViz[X] == K) {
Ctc[Ctc.size()-1].push_back(X);
GrViz[X] = N+1;
TrViz[X] = N+1;
}
for (int i = 0; i < Tr[X].size(); i++) {
if (TrViz[Tr[X][i]] < K) {
TrDfs(Tr[X][i]);
}
}
}
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);
Tr[Y].push_back(X);
}
for (int i = 1; i <= N; i++) {
if (GrViz[i] < K) {
GrDfs(i);
Ctc.resize(Ctc.size() + 1);
TrDfs(i);
K++;
}
}
cout << Ctc.size() << endl;
for (int i = 0; i < Ctc.size(); i++) {
for (int j = 0; j < Ctc[i].size(); j++) {
cout << Ctc[i][j] << " ";
}
cout << "\n";
}
return 0;
}