Pagini recente » Cod sursa (job #384746) | Cod sursa (job #313087) | Cod sursa (job #1967069) | Cod sursa (job #807688) | Cod sursa (job #883584)
Cod sursa(job #883584)
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int>::iterator it;
const int MAX_N = 100005;
vector<int> G[MAX_N], GT[MAX_N];
int N, V[MAX_N], TSort[MAX_N];
vector< vector<int> > SCC;
void DFP(int X) {
++V[X];
for (it Y = G[X].begin(); Y != G[X].end(); ++Y)
if (V[*Y] == 0)
DFP(*Y);
TSort[++TSort[0]] = X;
}
void DFM(int X, vector<int> &Component) {
Component.push_back(X);
--V[X];
for (it Y = GT[X].begin(); Y != GT[X].end(); ++Y)
if (V[*Y] == 1)
DFM(*Y, Component);
}
void Kosaraju() {
for (int X = 1; X <= N; ++X)
if (V[X] == 0)
DFP(X);
reverse(TSort + 1, TSort + TSort[0] + 1);
for (int i = 1; i <= TSort[0]; ++i) {
int X = TSort[i];
if (V[X] == 1) {
vector<int> Component;
DFM(X, Component);
SCC.push_back(Component);
}
}
}
void Read() {
assert(freopen("ctc.in", "r", stdin));
int M; assert(scanf("%d %d", &N, &M) == 2);
for (; M > 0; --M) {
int X, Y; assert(scanf("%d %d", &X, &Y) == 2);
G[X].push_back(Y); GT[Y].push_back(X);
}
}
void Print() {
assert(freopen("ctc.out", "w", stdout));
printf("%d\n", static_cast<int>(SCC.size()));
for (size_t i = 0; i < SCC.size(); ++i) {
for (it X = SCC[i].begin(); X != SCC[i].end(); ++X)
printf("%d ", *X);
printf("\n");
}
}
int main() {
Read();
Kosaraju();
Print();
return 0;
}