Cod sursa(job #363717)

Utilizator amadaeusLucian Boca amadaeus Data 14 noiembrie 2009 12:38:05
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 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];

int DFS( int v )
{
	u[v]=1;
	for(int i=0;i<a[v].size();i++)
		if(!u[a[v][i]])
			DFS( a[v][i] );
	t[v]=ct++;
}


int DFS2( int v )
{
	u[v]=cc;
	for(int i=0; i<gt[v].size();i++)
		if(!u[gt[v][i]])
			DFS2( gt[v][i] );
}


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[i] )
			cc++;
			DFS2( 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;
}