Cod sursa(job #361489)

Utilizator BaduBadu Badu Badu Data 5 noiembrie 2009 14:22:11
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 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);
vector <vector <int> > s(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();
	s[nr].pb( nd );
	v[nd]=0;
	for( i = 0; i< dim; i++)
		if(v[ t[nd][i] ]) DFST( t[nd][i] );

}

int main(){

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

	DATA();
	int i,j,dim;

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

	for(i=n; i>0; i--)
		if(v[d[i]]==1) {nr++;DFST(d[i]);}

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

	return 0;
}