Pagini recente » Cod sursa (job #2849338) | Cod sursa (job #2295942) | Cod sursa (job #1729422) | Cod sursa (job #759372) | Cod sursa (job #1164395)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define FILEIN "ctc.in"
#define FILEOUT "ctc.out"
#define NMAX 100005
vector<int> G[NMAX], GT[NMAX];
vector<int> Comp[NMAX];
int CompCnt;
int N, M;
vector<int> Sortare;
bool Used[NMAX];
void DFSort(int x) {
Used[x] = 1;
for ( int i = 0; i < G[x].size(); i++ ) {
if (!Used[G[x][i]]) {
DFSort(G[x][i]);
}
}
Sortare.push_back(x);
}
void DFFinal(int x, int comp) {
Used[x] = 1;
Comp[comp].push_back(x);
for ( int i = 0; i < GT[x].size(); i++ ) {
if (!Used[GT[x][i]])
DFFinal(GT[x][i], comp);
}
}
int main() {
freopen(FILEIN, "r", stdin);
freopen(FILEOUT, "w", stdout);
scanf("%d %d", &N, &M);
for ( int i = 1, x, y; i <= M; i++ ) {
scanf("%d %d", &x, &y);
G[x].push_back(y);
GT[y].push_back(x);
}
for ( int i = 1; i <= N; i++ ) {
if (!Used[i])
DFSort(i);
}
reverse(Sortare.begin(), Sortare.end());
memset(Used, 0, sizeof(Used));
for ( int i = 0; i < N; i++ ) {
if (!Used[Sortare[i]])
DFFinal(Sortare[i], ++CompCnt);
}
printf("%d\n", CompCnt);
for ( int i = 1; i <= CompCnt; i++ ) {
for ( int j = 0; j < Comp[i].size(); j++)
printf("%d ", Comp[i][j]);
printf("\n");
}
return 0;
}