Cod sursa(job #144545)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 27 februarie 2008 19:17:34
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <string>
#define MAX_N 50000
#define FIN "sortaret.in"
#define FOUT "sortaret.out"
using namespace std;
struct list{
        int inf;
        list* urm;
} *rel[MAX_N+1];
int m,n;
int sol[MAX_N+1],nrsol=0;
int used[MAX_N+1];

void iofile(void){
        freopen(FIN,"rt",stdin);
        freopen(FOUT,"wt",stdout);
        memset(used,0,sizeof(used));
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++){
                rel[i]=0;
        }
        list* q;
        for (int i=1,x,y;i<=m;i++){
                scanf("%d%d",&x,&y);
                q=new list;
                q->inf=y;
                q->urm=rel[x];
                rel[x]=q;
        }
        fclose(stdin);
}


void df(int i){
        list *q;
        q=rel[i];
        while (q){
                if (!used[q->inf]){
                        used[q->inf]=1;
                        df(q->inf);
                }
                q=q->urm;
        }
        sol[++nrsol]=i;
}


int main(void){
        iofile();
        for (int i=1;i<=n;i++){
                if (!used[i]){used[i]=1;df(i);}
        }
        for (int i=nrsol;i>1;i--){
                printf("%d ",sol[i]);
        }
        printf("%d\n",sol[1]);
        fclose(stdout);
        return 0;
}