Cod sursa(job #497855)

Utilizator klamathixMihai Calancea klamathix Data 3 noiembrie 2010 13:00:29
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 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;
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]);
			t[node] = max ( t[node] , t[G2[node][i]]) ;
	}
	if ( G2[node].size() ) t[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);
		top[i] = i;
	}
		
	memset( seen , 0 , sizeof(seen));
	sort ( top + 1, top + n + 1 , cmp());
	
	for( i = 1 ; i <= n ; ++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;
}