Pagini recente » Cod sursa (job #1536133) | Cod sursa (job #1052982) | Cod sursa (job #2912899) | Cod sursa (job #2342542) | Cod sursa (job #780811)
Cod sursa(job #780811)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int kMaxN = 100005;
vector<int> G[kMaxN], GT[kMaxN];
int N, TSort[kMaxN], V[kMaxN];
vector< vector<int> > SCC;
vector<int> C;
void DFP(const int X) {
++V[X];
for(vector<int>::iterator Y = G[X].begin(); Y != G[X].end(); ++Y)
if (!V[*Y])
DFP(*Y);
TSort[++TSort[0]] = X;
}
void DFM(const int X) {
C.push_back(X);
--V[X];
for (vector<int>::iterator Y = GT[X].begin(); Y != GT[X].end(); ++Y)
if (V[*Y])
DFM(*Y);
}
void Kosaraju() {
for (int X = 1; X <= N; ++X)
if (!V[X])
DFP(X);
reverse(TSort+1, TSort+N+1);
for (int i = 1; i <= N; ++i) {
int X = TSort[i];
if (V[X]) {
C.clear();
DFM(X);
SCC.push_back(C);
}
}
}
void Read() {
freopen("ctc.in", "r", stdin);
int M; scanf("%d %d", &N, &M);
for (; M; --M) {
int X, Y; scanf("%d %d", &X, &Y);
G[X].push_back(Y);
GT[Y].push_back(X);
}
}
void Print() {
freopen("ctc.out", "w", stdout);
printf("%d\n", SCC.size());
for (int i = 0; i < SCC.size(); ++i) {
for (int j = 0; j < SCC[i].size(); ++j)
printf("%d ", SCC[i][j]);
printf("\n");
}
}
int main() {
Read();
Kosaraju();
Print();
return 0;
}