Cod sursa(job #330397)

Utilizator irene_mFMI Irina Iancu irene_m Data 9 iulie 2009 20:42:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <vector>
#define MaxN 100009

using namespace std;

vector <int> suc[MaxN],pred[MaxN],sol[MaxN];
int n,m,uz[MaxN],c[MaxN],nr,sz;

void cit()
{
	int i,x,y;
	freopen("ctc.in","r",stdin);
	scanf("%d%d",&n,&m);
	
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		suc[x].push_back(y);
		pred[y].push_back(x);
	}
}

void dfs(int nod)
{
	int i,p;
	uz[nod]=1;
	
	for(i=0;i<suc[nod].size();i++)
	{
		p=suc[nod][i];
		if(!uz[p])
			dfs(p);
	}
	
	sz++;
	c[sz]=nod;
}

void df(int nod,int nr)
{
	int i,p;
	uz[nod]=1;
	
	sol[nr].push_back(nod);

	for(i=0;i<pred[nod].size();i++)
	{
		p=pred[nod][i];
		if(!uz[p])
			df(p,nr);
	}
}	

void afis()
{
	int i,j;
	freopen("ctc.out","w",stdout);
	printf("%d\n",nr);
	for(i=1;i<=nr;i++)
	{
		for(j=0;j<sol[i].size();j++)
			printf("%d ",sol[i][j]);
		printf("\n");
	}
}

int main()
{
	cit();
	for(int i=1;i<=n;i++)
		if(!uz[i])
			dfs(i);
		
	memset(uz,0,sizeof(uz));
	
	for(int i=sz;i;i--)
		if(!uz[c[i]])
		{
			nr++;
			df(c[i],nr);
		}
		
	afis();

	return 0;
}