Cod sursa(job #383848)

Utilizator alexeiIacob Radu alexei Data 18 ianuarie 2010 11:51:36
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#include<vector>
#include<deque>
using namespace std;
#define NMAX 100004

vector< int >G[NMAX];

int UPP[NMAX],DOWN[NMAX];

deque< int >S;

bool viz[NMAX],in_S[NMAX];

int ANS,index;

vector< int >SOL[NMAX];

//Decebal's fist

void traian( int nod )
{
	++index;
	UPP[ nod ]=index;
	DOWN[ nod ]=index;
	
	S.push_back( nod );
	in_S[nod]=1;
	
	for( vector< int >::iterator it=G[nod].begin(); it!=G[nod].end(); ++it )
	{
		if( !UPP[ *it ] )
		{
			traian( *it );
			
			DOWN[ nod ]=min( DOWN[ nod ], DOWN[*it] );
		}
		else
		{
			if( in_S[ *it ] )
			DOWN[ nod ]=min( DOWN[ nod ], DOWN[ *it ] );
		}
	}
	
	if( UPP[ nod ]==DOWN[ nod ] )
	{
		++ANS;
		int node;
		do{
			node=S.back();
			S.pop_back();
			in_S[node]=0;
			
			SOL[ANS].push_back( node );
		}while( node!=nod );
	}
}
	
void show()
{
	printf("%d\n",ANS);
	
	int i;
	for(i=1; i<=ANS; ++i)
	{
		for( vector< int >::iterator it=SOL[i].begin(); it!=SOL[i].end(); ++it )
			printf("%d ",*it);
		printf("\n");
	}
}		

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	
	int N,M;
	scanf("%d%d",&N,&M);
	
	int i,a1,a2;
	for(i=1; i<=M; ++i)
	{
		scanf("%d%d",&a1,&a2);
		G[a1].push_back(a2);
	}
	
	for(i=1; i<=N; ++i)
		if( !UPP[i] )
			traian( i );
		
		
	show();
		
	return 0;
}