Cod sursa(job #360404)

Utilizator MihaiGmihaig MihaiG Data 31 octombrie 2009 13:26:32
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <stdio.h>
#include <vector>
#define NMAX 100000
using namespace std;
FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");
int i,j,n,m,nod,nod2,nr,viz[NMAX],postord[NMAX];
vector <int> graf[NMAX];
vector <int> graft[NMAX];
vector <int> solutie[NMAX];
void citire(){
	fscanf(f,"%d %d",&n,&m);
	for(i=0;i<m;i++){
		fscanf(f,"%d %d",&nod,&nod2);
		graf[nod].push_back(nod2);
		graft[nod2].push_back(nod);
	}
}
void dfs(int x){
	viz[x]=1;
	for(j=0;j<graf[x].size();j++){
		if(!viz[graf[x][j]]){
			dfs(graf[x][j]);
		}
	}
	postord[++nr]=x;
}
void dfst(int x){
	viz[x]=0;
	solutie[nr].push_back(x);
	for(j=0;j<graft[x].size();j++){
		if(viz[graft[x][j]]){
			dfst(graft[x][j]);
		}
	}
}
void afis(){
	fprintf(g,"%d\n",nr);
	for(i=1;i<=nr;i++){
		for(j=0;j<solutie[i].size();j++){
			fprintf(g,"%d ",solutie[i][j]);
		}
		fprintf(g,"\n");
	}
}
int main(){
	
	citire();
	for(i=1;i<=n;i++){
		if(!viz[i]){
			dfs(i);
		}
	}
	nr=0;
	for(i=n;i>=1;i--){
		if(viz[postord[i]]){
			nr++;
			dfst(postord[i]);
		}
	}
	afis();
	
	fclose(f);
	fclose(g);
	return 0;
}