Cod sursa(job #1481855)

Utilizator sddddgjdZloteanu Anastasia sddddgjd Data 5 septembrie 2015 13:30:25
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<stdio.h>
int edges[100001],next[100001],last[50001],first[50001],viz[50001],coada[50001],nr;
void dfs(int nod){
    int p=first[nod];
    viz[nod]=1;
    coada[nr++]=nod;
    while(p!=0){
        if(viz[edges[p]]==0)
            dfs(edges[p]);
        p=next[p];
    }
}
int main(){
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    int i,cont=1;
    for(i=0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(first[x]==0){
            first[x]=cont;
            last[x]=cont;
        }
        else{
            next[last[x]]=cont;
            last[x]=cont;
        }
        edges[cont++]=y;
    }
    for(i=1;i<=n;i++)
        if(viz[i]==0)
            dfs(i);
    for(i=0;i<n;i++)
        printf("%d ",coada[i]);
    return 0;
}