Cod sursa(job #562200)

Utilizator avram_florinavram florin constantin avram_florin Data 22 martie 2011 16:45:08
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<fstream>
#include<cstdio>
#include<vector>

using namespace std;

const int MaxN = 100001;

int n,m,timp=1,nr,tf[MaxN],viz[MaxN],ord[MaxN];
vector<int> G[MaxN],GT[MaxN],CC[MaxN];

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

void ordine()
{
	for( int i = 1 ; i <= n ; i++ )
		if( !viz[i] )
			{
				int k = tf[i];
				ord[n-k+1] = i;
			}
}

void dfst(int nod)
{
	vector<int>::iterator it = GT[nod].begin(),iend = GT[nod].end();
	viz[nod] = nr;
	CC[nr].push_back(nod);
	for( ; it != iend ; ++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_tf(i);
	memset(viz,0,sizeof(viz));
	ordine();
	for( i = 1 ; i <= n ; i++ )
		{
			x = ord[i];
			if( !viz[x] )
				{
					nr++;
					dfst(x);
				}
		}
	printf("%d\n" , nr);
	for( i = 1 ;i <= nr ; i++ )
		{
			vector<int>::iterator it = CC[i].begin(),iend = CC[i].end();
			for( ; it != iend ; ++it )
				printf("%d " , *it);
			printf("\n");
		}
	return 0;
}