Cod sursa(job #286879)

Utilizator razyelxrazyelx razyelx Data 24 martie 2009 11:50:34
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream.h>
#include <stdlib.h>
#define Nmax 50001
ifstream in("sortaret.in");
ofstream out("sortaret.out");

int postordine[Nmax],nr,viz[Nmax],n,m;
int * A[Nmax];

void citeste(){
     int i,x,y;
     in>>n>>m;

     for(i=1;i<=n;++i){
	A[i] = (int *)realloc(A[i],sizeof(int));
	A[i][0] = 0;
     }
     for(i=1;i<=m;++i){
	in>>x>>y;
	A[x][0]++;
	A[x] = (int *)realloc(A[x],(A[x][0]+1)*sizeof(int));
	A[x][A[x][0]] = y;
     }
}
void dfs(int x){
     viz[x] = 1;
     for(int i=1;i<=A[x][0];++i)
	if(!viz[A[x][i]])
	  dfs( A[x][i] );
     postordine[++nr] = x;
}
void sortare_t(){
     for(int i=1;i<=n;++i)
	if(!viz[i])
	  dfs( i );
}
void afisare(){
     for(int i=nr;i>0;--i)
	out<<postordine[i]<<" ";
}
int main(){
    citeste();
    sortare_t();
    afisare();
    return 0;
}