Cod sursa(job #360425)

Utilizator MihaiGmihaig MihaiG Data 31 octombrie 2009 14:39:51
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <stdio.h>
#include <vector>
#define NMAX 100001
using namespace std;
FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");
int i,nr,n,m,viz[NMAX],postord[NMAX],nod,nod2;
vector <int> graf[NMAX],graft[NMAX],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;
	int j;
	for(j=0;j<graf[x].size();j++){
		if(!viz[graf[x][j]]){
			dfs(graf[x][j]);
		}
	}
	postord[++nr]=x;
}

void dfst(int x){
	int j;
	graf[nr].push_back(x);
	viz[x]=0;
	for(j=0;j<graf[x].size();j++){
		if(viz[graf[x][j]]){
			dfst(graf[x][j]);
		}
	}
}

void afis(){
	int j;
	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>0;i--){
		if(viz[i]){
			nr++;
			dfst(i);
		}
	}
	afis();
	
	fclose(f);
	fclose(g);
	return 0;
}