Cod sursa(job #1712740)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 3 iunie 2016 16:24:27
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define N 50100
#define M 100100
#define vec lis[i].val

using namespace std;

int head[N],ifin,postnum[N],viz[N];
int stk[N],sp;

void Add_arc(int x,int y);

struct muc{
    int val,next;
};
struct muc lis[M];

void push(int x){
    stk[sp++]=x;
}

int pop(){
    return stk[--sp];
}

int cnt;
void dfs(int k){
    int i;

    viz[k]=1;
    for(i=head[k];i!=-1;i=lis[i].next){
        if(viz[vec]==0){
            dfs(vec);
        }
    }
    postnum[k]=++cnt;
    push(k);
}

int main(){
    int i,n,m,x,y;

    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

    scanf("%d%d",&n,&m);

    memset(head,-1,(n+1)*sizeof(int));



    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        Add_arc(x,y);
    }

    for(i=1;i<=n;i++){
        if(viz[i]==0){
            dfs(i);
        }
    }
    for(i=0;i<n;i++){
        printf("%d ",pop() );
    }


    return 0;
}


void Add_arc(int x,int y){
    lis[ifin].val=y;
    lis[ifin].next=head[x];
    head[x]=ifin;
    ifin++;
}