Cod sursa(job #497935)

Utilizator klamathixMihai Calancea klamathix Data 3 noiembrie 2010 17:49:12
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
const int maxn = 100005;
using namespace std;

int i , j , k , t[maxn] , a , b , n , m  , top[maxn] , ans , v;
vector <int> G[maxn] , G2[maxn] , L[maxn];
bool seen[maxn];

struct cmp { bool operator () ( const int &a , const int &b ) {
	return (t[a] > t[b] );
	}
};

void DF1 (int node)
{
	int i;
	seen[node] = 1;
	for( i = 0 ; i < G2[node].size() ; ++i ) 
		if ( !seen[G2[node][i]]) 
			DF1(G2[node][i]);
		top[++v] = node;

}

void DF2( int node ) {
	int i;
	seen[node] = 1;
	L[ans].push_back(node);
	
	for( i = 0 ; i < G[node].size() ; ++i ) 
		if ( !seen[G[node][i]]) 
			DF2(G[node][i]);
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	for( i = 1 ; i <= m ; ++i ) {
		scanf("%d %d",&a,&b);
		G[a].push_back(b);
		G2[b].push_back(a);
	}

	for( i = 1 ; i <= n ; ++i ) 
		t[i] = 0;
	
	for( i = 1 ; i <= n ; ++i ) { 
		if ( !seen[i] ) 
			DF1(i);
	}
	memset(seen,0,sizeof(seen));
	
	for( i = n ; i >= 1 ; --i ) {
		if ( !seen[top[i]]) {
			ans ++;
			DF2(top[i]);
		}
	}
	
	printf("%d\n",ans);
	for( i = 1 ; i <= ans ; ++i ) {
		for( j = 0 ; j < L[i].size() ; ++j)
			printf("%d ",L[i][j]);
		printf("\n");
	}
	
return 0;
}