Cod sursa(job #396451)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 15 februarie 2010 13:34:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
#define Nmx 50001

int n,m;
int Q[Nmx],grd[Nmx];

struct nod
{
    int x;
    nod *urm;
};

nod *G[Nmx];

void add(int x,int y)
{
    nod *aux=new nod;
    aux->urm=G[x];
    aux->x=y;
    G[x]=aux;
}

void citire()
{
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y);grd[y]++;
    }
}


void solve()
{
    for(int i=1;i<=n;++i)
        if(grd[i]==0)
            Q[++Q[0]]=i;
    for(int i=1;i<=Q[0];++i)
    {
        for(nod *p=G[Q[i]];p;p=p->urm)
        {
            grd[p->x]--;
            if(grd[p->x]==0)
                Q[++Q[0]]=p->x;
        }
    }
    for(int i=1;i<=Q[0];++i)
        printf("%d ",Q[i]);
    printf("\n");
}

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    citire();
    solve();
    return 0;
}