Cod sursa(job #413109)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 7 martie 2010 18:07:09
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<iostream>
#include<string>
#include<vector>

using namespace std;

#define NM 100005

vector<int> G[NM],GT[NM],CT[NM];

char viz[NM];
int p[NM],dim,ctc;

void DF(int nod)
{
	viz[nod]=1;
	
	for(int i=0;i<G[nod].size();++i)
	{
		int nnod=G[nod][i];
		if(!viz[nnod]) DF(nnod);
	}	
	
	p[++dim]=nod;
}

void DFT(int nod)
{
	viz[nod]=0;
	CT[ctc].push_back(nod);
	//printf("%d\n",nod);
	
	for(int i=0;i<GT[nod].size();++i)
	{
		int nnod=GT[nod][i];
		if(viz[nnod]) DFT(nnod);
	}	
}

int main()
{
	int N,M,a,b;
	
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	
	scanf("%d %d",&N,&M);
	
	for(int i=1;i<=M;++i)
	{
		scanf("%d %d",&a,&b);
		
		G[a].push_back(b);
		GT[b].push_back(a);
	}	
	
	for(int i=1;i<=N;++i)
		if(!viz[i]) DF(i);
	
	for(int i=N;i>=1;--i)
		if(viz[p[i]]) 
		{	
			++ctc;
			DFT(p[i]);
		}	
	
	printf("%d\n",ctc);	
		
	for(int i=1;i<=ctc;++i)	
	{
		for(int j=0;j<CT[i].size();++j)
			printf("%d ",CT[i][j]);
		
		printf("\n");
    }
	
	return 0;
}