Cod sursa(job #236376)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 27 decembrie 2008 12:25:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#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;
}