Pagini recente » Cod sursa (job #2678766) | Cod sursa (job #2233238) | Cod sursa (job #1734529) | Cod sursa (job #2178757) | Cod sursa (job #304438)
Cod sursa(job #304438)
//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],*prim; //Lista de adiacenta;
char viz[MaxN]; //Vectorul caracteristic Viz al nodurilor deja vizitate.
void adauga_inceput(int Vf1,int Vf2);
void dfs(int x);
void add_start(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] == 0)
dfs(i);
};
for(nod *p=prim;p!=NULL;p=p->urm)
fprintf(g,"%d ",p->inf);
};
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){
viz[x]=1;
for (nod *p=L[x];p!=NULL;p=p->urm)
if (viz[p->inf] == 0)
dfs(p->inf);
viz[x]=2;
add_start(x);
};
void add_start(int x){
nod *p=new nod;
p->inf=x;
p->urm=prim;
prim=p;
};