Cod sursa(job #926935)

Utilizator dragangabrielDragan Andrei Gabriel dragangabriel Data 25 martie 2013 14:21:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<cstdio>
#include<vector>
#define nmax 100005
using namespace std;
int n,i,j,k,transpus[nmax],rez,m,x,y;
bool viz[nmax];
vector<int>A[nmax],B[nmax],C[nmax];

void DF(int x)
{
	viz[x]=true;
	for (int j=0;j<A[x].size();j++) 
		if (!viz[A[x][j]])
			DF(A[x][j]);
	transpus[++m]=x;
}

void DFT(int x)
{
	viz[x]=false;
	C[rez].push_back(x);
	for (int j=0;j<B[x].size();j++)
		if (viz[B[x][j]])	
			DFT(B[x][j]);
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=m;i++)
		{
			scanf("%d %d",&x,&y);
			A[x].push_back(y);
			B[y].push_back(x);
			}
	
	m=0;
	for (i=1;i<=n;i++)  
		if (!viz[i]) 
			DF(i);
	for (i=n;i>=1;i--)	
		if (viz[transpus[i]])		
			{		
				rez++;
				DFT(transpus[i]);
			}
	printf("%d\n",rez);
	for (i=1;i<=rez;i++)
	{
		for (j=0;j<C[i].size();j++) 
			printf("%d ",C[i][j]);
		printf("\n");	
	}	
	return 0;
}