Cod sursa(job #1814280)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 23 noiembrie 2016 20:17:01
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.93 kb
#include <stdio.h>
#include <stdlib.h>
int nr,lista[50001],nod[100001],next[100001],coada[50001],pred[50001];
void add(int x,int y)
{
    nr++;
    nod[nr]=y;
    next[nr]=lista[x];
    lista[x]=nr;
}
int main()
{
    int n,m,i,x,y,u,p;
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        pred[y]++;
    }
    u=0;
    for(i=1; i<=n; i++)
        if(pred[i]==0)
            coada[++u]=i;
    p=1;
    while(p<=u)
    {
        x=lista[coada[p]];
        while(x)
        {
            if(pred[nod[x]]!=0)
            {
                pred[nod[x]]--;
                if(pred[nod[x]]==0)
                    coada[++u]=nod[x];
            }
            x=next[x];
        }
        p++;
    }
    for(p=1; p<=u; p++)
        printf("%d ",coada[p]);

    return 0;
}