Pagini recente » Cod sursa (job #3211795) | Cod sursa (job #2070622) | Cod sursa (job #2978955) | Cod sursa (job #2217947) | Cod sursa (job #1090283)
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int Vmax = 100000;
vector<int> G[Vmax], Gt[Vmax], fin, results[Vmax];
bool use[Vmax]; int C;
void dfs(int x) {
use[x] = 1;
for (vector<int>::iterator it = Gt[x].begin(); it != Gt[x].end(); ++it) {
if (use[*it] == 0) {
dfs(*it);
}
}
fin.push_back(x);
}
void dfs2(int x) {
use[x] = 1;
for (vector<int>::iterator it = Gt[x].begin(); it != Gt[x].end(); ++it) {
if (use[*it] == 0) {
dfs2(*it);
}
}
results[C].push_back(x);
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int V, E, i, x, y;
scanf("%d%d", &V, &E);
for (i = 0; i < E; ++i) {
scanf("%d%d", &x, &y);
G[x] .push_back(y);
Gt[y].push_back(x);
}
memset(use, false, sizeof(use));
fin.reserve(V);
for (i = 1; i <= V; ++i) {
if (use[i] == 0) {
dfs(i);
}
}
memset(use, false, sizeof(use));
C = 0;
for (vector<int>::iterator it = fin.begin(); it != fin.end(); ++it) {
if (use[*it] == 0) {
dfs2(*it);
++C;
}
}
printf("%d\n", C);
for (i = 0; i < C; ++i) {
for (vector<int>::iterator it = results[i].begin(); it != results[i].end(); ++it) {
printf("%d ", *it);
}
printf("\n");
}
return 0;
}