Cod sursa(job #555755)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 15 martie 2011 19:04:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<stdio.h>
#include<vector>
#define Nmax 100010
using namespace std;

int n,m,viz[Nmax],i,a,b,ctc,S[Nmax],nn,N,j;

vector<int> G[Nmax],T[Nmax],Ctc[Nmax];

void sortaret ( int nod ) 
{
	int i, N = G[nod].size() ; 
	
	viz[nod] = 1 ;
	
	for( i = 0 ; i < N ; i++ )
		if( !viz[ G[nod][i] ] ) sortaret( G[nod][i] ) ;
	
	S[--nn] = nod ; 
}

void dfs ( int nod ) 
{
	int i, N = T[nod].size() ; 
	
	Ctc[ctc].push_back(nod);
	viz[nod] = 0 ;
	
	for( i = 0 ; i < N ; i++ )
		if( viz[ T[nod][i] ] ) dfs( T[nod][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);
		T[b].push_back(a);
	}
	
	nn = n + 1 ;
	for( i = 1 ; i <= n ; i++ )
		if( !viz[i] ) sortaret(i);
	
	for( i = 1 ; i <= n ; i++ )
		if( viz[ S[i] ] )  ctc++, dfs( S[i] ) ;

	printf("%d\n",ctc);

	for( i = 1 ; i <= ctc ; i++ )
	{
		N = Ctc[i].size();
		
		for( j = 0 ; j < N ; j++ )
			printf("%d ",Ctc[i][j]);
		printf("\n");
	}
	
	return 0 ;
}