Cod sursa(job #2016300)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 29 august 2017 04:26:12
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdlib.h>
#include <stdio.h>

typedef struct nod{
    int val;
    struct nod *next; } nod;

nod *push_front(nod *n, const int val){
    nod *x = (nod*)malloc(sizeof(nod));
    x->next = n;
    x->val = val;
    return x; }

#define MAXN (50000+10)

nod *vec[MAXN] = {};
int nr_prevs[MAXN] = {}, st[MAXN], *st_p = st, rez[MAXN], *rez_p = rez;

int main(){
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    int n, m;
    scanf("%d %d", &n, &m);

    for(int i = 0, x, y; i < m; ++i){
        scanf("%d %d", &x, &y);
        --x, --y;
        vec[x] = push_front(vec[x], y);
        ++nr_prevs[y]; }
    for(int i = 0; i < n; ++i)
        if(nr_prevs[i] == 0)
            *st_p++ = i;
    while(st_p != st){
        const int cur = *--st_p;
        *rez_p++ = cur;
        for(nod *n = vec[cur]; n; n = n->next)
            if(--nr_prevs[n->val] == 0)
                *st_p++ = n->val; }
    for(int *p = rez; p < rez_p; ++p)
        printf("%d ", *p + 1);
    return 0; }