Cod sursa(job #304434)

Utilizator cvicentiuCiorbaru Vicentiu Marian cvicentiu Data 13 aprilie 2009 08:49:20
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
//Sortare Topologica (Graf Aciclic Orientat)
#include <stdio.h>
#define MaxN 50001
#define fin "sortaret.in"
#define fout "sortaret.out"
FILE *f = fopen(fin,"r");
FILE *g = fopen(fout,"w");
int n,m;							//nr Vf Nr Muchii
struct nod {						//structura de nod
	int inf;
	nod *urm;
};
nod *L[MaxN];						//Lista de adiacenta;
char viz[MaxN];						//Vectorul caracteristic Viz al nodurilor deja vizitate.
void adauga_inceput(int Vf1,int Vf2);
void dfs(int x);
int main(){
	fscanf(f,"%d %d",&n,&m);			//Citirea Numarului Noduri, Muchii
	for (int i=1;i<=n;i++){			//Citirea Muchiilor, introducerea in lista de adiacenta
		int ex1,ex2;
		fscanf(f,"%d %d",&ex1,&ex2);
		adauga_inceput(ex1,ex2);
	};
	for(int i=1;i<=n;i++){			//Parcurgem tot graful, in cazul in care acesta este sau nu conex;
		if (!viz[i])
			dfs(i);
		};
};

void adauga_inceput(int Vf1,int Vf2){
	nod *p=new nod;
	p->inf=Vf2;
	p->urm=L[Vf1];
	L[Vf1]=p;
};
void dfs(int x){
	fprintf(g,"%d ",x);
	viz[x]=1;
	for (nod *p=L[x];p!=NULL;p=p->urm){
		if (!viz[p->inf])
			dfs(p->inf);
	};
};