Pagini recente » Cod sursa (job #2208192) | Cod sursa (job #2884479) | Cod sursa (job #1322114) | Cod sursa (job #2816647) | Cod sursa (job #236376)
Cod sursa(job #236376)
#include <cstdio>
#include <vector>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
int N, M, k, nr;
vvi G, Gt, Comp;
vb U;
vi Start, tmp;
void load() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &N, &M);
G.resize( N+1 ); Gt.resize( N+1 );
U.resize( N+1 );
while ( M-- ) {
int x, y;
scanf( "%d %d", &x, &y );
G[x].push_back(y);
Gt[y].push_back(x);
}
}
void DF1( int x ) {
if ( U[x] ) return;
U[x] = true;
for ( vi::iterator it=G[x].begin(); it!=G[x].end(); ++it )
DF1( *it );
Start.push_back(x);
}
void DF2( int x ) {
if ( U[x] ) return ;
U[x] = true;
tmp.push_back(x);
for ( vi::iterator it=Gt[x].begin(); it!=Gt[x].end(); ++it )
DF2( *it );
}
void ctc() {
for ( int i=1; i<=N; ++i ) U[i] = false;
for ( int i=1; i<=N; ++i ) DF1(i);
for ( int i=1; i<=N; ++i ) U[i] = false;
for ( int i=N-1; i>=0; --i )
if ( U[Start[i]] == false ) {
tmp.clear();
DF2(Start[i]);
Comp.push_back(tmp);
++nr;
}
}
void output() {
printf("%d\n", nr);
for ( int i=0; i<nr; ++i ) {
for ( vi::iterator j=Comp[i].begin(); j!=Comp[i].end(); ++j )
printf("%d ",*j);
printf( "\n" );
}
}
int main() {
load();
ctc();
output();
return 0;
}