Cod sursa(job #361484)

Utilizator BaduBadu Badu Badu Data 5 noiembrie 2009 14:02:05
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<stdio.h>
#include<vector>
#define max 100001
#define pb push_back

using namespace std;

vector <vector <int> > g(max);
vector <vector <int> > t(max);
int n,m,nr,k,v[max],d[max];

void DATA(){

	int x,y;
	FILE *f=fopen("ctc.in","r");
	fscanf(f,"%d%d",&n,&m);

	for( ; m-- ; ){
		fscanf(f,"%d%d",&x,&y);
		g[x].pb(y);
		t[y].pb(x);
	}
}

void DFS( int nd ){
	
	int i,dim=g[nd].size();
	v[nd]=1;
	for( i = 0; i< dim; i++)
		if( ! v[ g[nd][i] ] ) DFS( g[nd][i] );
	d[++k] = nd;
}

void DFST( int nd ){
	
	int i,dim=t[nd].size();
	v[nd]=0;
	for( i = 0; i< dim; i++)
		if(v[ t[nd][i] ]) DFST( t[nd][i] );
	g[nr].pb( nd );
}

int main(){

	FILE *o=fopen("ctc.out","w");

	DATA();
	int i,j,dim;

	for(i=1;i<=n;i++)
		if(!v[i]) DFS(i);

	g.clear();

	for(i=1; i<=n; i++)
		if(v[i]==1) {nr++;DFST(i);}

	fprintf(o,"%d\n",nr);
	for(i=1;i<=nr;i++){ dim=g[i].size();
		for(j=0;j<dim;j++) fprintf(o,"%d ",g[i][j]);
		fprintf(o,"\n");
	}

	return 0;
}