Cod sursa(job #870293)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 3 februarie 2013 08:45:22
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<stdio.h>

int n,m,start[50002], t[2][100002];
int s,x,y,i,j,z;

int stiva[50002],v[50002];
int viz[50002],nr;

void dfs(int vf){
    int k,x,y,j;
    stiva[1]=vf;
    k=1;
    viz[vf]=1;
    while(k>0){
        x=stiva[k];
        for(j=start[x];j!=0;j=t[1][j]){
            y=t[0][j];
            if(viz[y]==0){
                break;
            }
        }
        if(j!=0){
            k++;
            stiva[k]=y;
            viz[y]=1;
        }
        else{
            nr++;
            v[nr]=stiva[k];
            k--;
        }
    }
}
int main(){
    freopen("sortaret.in","rt",stdin);
    freopen("sortaret.out","wt",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++){
        start[i]=0;
        viz[i]=0;
    }
    j=0;
    for (i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        j++;
        t[0][j]=y;
        t[1][j]=start[x];
        start[x]=j;
    }
    nr=0;
    dfs(1);
    for(i=nr;i>=1;i--) printf("%d ",v[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}