Cod sursa(job #562221)

Utilizator avram_florinavram florin constantin avram_florin Data 22 martie 2011 17:12:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<cstdio>
#include<fstream>
#include<vector>

using namespace std;

const int MaxN = 100001;

int n,m,nrc,end,viz[MaxN],timp[MaxN];
vector<int> G[MaxN],Gt[MaxN],CC[MaxN];

void DFS(int nod)
{
	vector<int>::iterator I = G[nod].begin(),IE = G[nod].end();
	viz[nod] = 1;
	for( ; I != IE ; ++I )
		if( !viz[*I] )
			DFS(*I);
	timp[++end] = nod;
}

void DFSt(int nod)
{
	vector<int>::iterator It = Gt[nod].begin(),IEt = Gt[nod].end();
	viz[nod] = 1;
	CC[nrc].push_back(nod);
	for( ; It != IEt ; ++It )
		if( !viz[*It] )
			DFSt(*It);
}

int main()
{
	freopen("ctc.in" , "r" , stdin );
	freopen("ctc.out" , "w" , stdout );
	scanf("%d%d" , &n , &m );
	int i,x,y;
	for( i = 1 ; i <= m ; i++ )
		{
			scanf("%d%d" , &x , &y);
			G[x].push_back(y);
			Gt[y].push_back(x);
		}
	for( i = 1 ; i <= n ; i++ )
		if( !viz[i] )
			DFS(i);
	memset(viz,0,sizeof(viz));
	for( i = n ; i ; i-- )
		if( !viz[timp[i]] )
			{
				nrc++;
				DFSt(timp[i]);
			}
	printf("%d\n" , nrc);
	for( i = 1 ; i <= nrc ; i++ )
		{
			vector<int>::iterator it = CC[i].begin(), iend = CC[i].end();
			for( ; it != iend ; ++it )
				printf("%d " , *it );
			printf("\n");
		}
	return 0;
}