Cod sursa(job #2668206)

Utilizator Edwuard99Diaconescu Vlad Edwuard99 Data 4 noiembrie 2020 17:19:59
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct nod
{
    long v;
    nod *urm;
} *pnod;

#define NMAX 50010


pnod list[NMAX];
long n, m, grad[NMAX];

inline void baga(long x, long y)
{
    pnod aux;
    aux = new nod;
    aux -> v = y;
    aux -> urm = list[x];
    list[x] = aux;
}

void read()
{
    long i, x, y;
    scanf("%ld %ld", &n, &m);
    while(m--)
    {
        scanf("%ld %ld", &x, &y);
        baga(x, y);
        ++grad[y];
    }
}

long c[NMAX];

void bf()
{
    pnod it;
    long x, i, next;
    long inc = 0, sf = 0;

    for(i = 1; i <= n; ++i)
        if(!grad[i]) c[++sf] = i;

    while(inc <= sf)
    {
        x = c[inc++];


        for(it = list[x]; it != NULL; it = it -> urm)
        {
            next = it -> v;
            --grad[next];
            if(!grad[next])
                c[++sf] = next;
        }
    }
}

int main()
{
    long i;
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    read();

    bf();

    for(i = 1; i <= n; ++i)
        printf("%ld ", c[i]);


    return 0;
}