Cod sursa(job #345484)

Utilizator aghamatMorariu Razvan aghamat Data 3 septembrie 2009 12:27:58
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>

#define DIM 50000

struct Nod{
    int x;
    Nod *adr;};
Nod *lst[DIM];
int nr, viz[DIM], ord[DIM];

void add (int A, int B)
{
    Nod *p;
    p=new Nod;
    p->adr=lst[A];
    p->x=B;
    lst[A]=p;   
}

void DF(int k)
{
    Nod *p;
    viz[k]=1;
    for (p=lst[k]; p; p=p->adr)
        if (!viz[p->x])
            DF(p->x);
    ord[++nr]=k;     
}

int main()
{
    int i, n, m, a, b;
    
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    
    scanf("%d%d",&n,&m);
    for (i=1; i<=m; ++i)
    {
        scanf("%d%d",&a,&b);
        add(a,b);    
    }
    
    for (i=1; i<=n; ++i)
        if (!viz[i])
            DF(i);
    
    for (i=n; i>0; --i)
        printf("%d ", ord[i]);
        
    return 0;    
}