Cod sursa(job #363719)

Utilizator amadaeusLucian Boca amadaeus Data 14 noiembrie 2009 12:51:27
Problema Componente tare conexe Scor 54
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define NX 100010

vector <int> a[NX];
vector <int> gt[NX];

int t[NX],n,m,ct=0,cc=0, u[NX], b[NX];

void DFS( int v )
{
	u[v]=1;
	for( vector<int>::iterator it = a[v].begin(); it!= a[v].end(); it++ )
		if( !u[*it] )
			DFS( *it );
	t[v]=ct++;
}


void DFS2( int v )
{
	u[v]=cc;
	for( vector<int>::iterator it = gt[v].begin(); it!= gt[v].end(); it++ )
		if( !u[*it] )
			DFS2( *it );
}


struct cmp {
	bool operator() ( const int x, const int y ) const {
		return t[x] > t[y];
	}
};


int main() 
{
	int i, v, w;
	freopen( "ctc.in", "r", stdin);
	freopen( "ctc.out", "w", stdout);
	scanf( "%d%d", &n, &m );
	
	for( i=0; i<m; i++)
	{
		scanf( "%d%d", &w, &v);
		
		a[w].push_back(v);
		gt[v].push_back(w);
	}
	
	for( i = 1; i <= n; i++ )
		if( !u[i] )
			DFS( i );
	
	for( i = 1; i <= n; i++ )
		sort( gt[i].begin(), gt[i].end(), cmp() );
	
	for( i = 1; i <= n; i++ ) {
		b[i] = i;
		u[i] = 0;
	}
	
	sort( b+1, b+n+1, cmp() );
	
	for( i = 1; i <= n; i++ ) {
		if( !u[ b[i] ] )
			cc++;
			DFS2( b[i] );
	}
	
	printf( "%d\n", cc );
	for( i = 1; i <= cc; i++ ) {
		for( int j = 1; j <= n; j++ )
			if( u[j] == i )
				printf( "%d ", j );
		printf( "\n" );
	}
	return 0;
}