Cod sursa(job #978585)

Utilizator stefanfStefan Fulger stefanf Data 29 iulie 2013 02:46:39
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.18 kb
#include<stdio.h>
#include<stdlib.h>

#define N 50005

struct node {
    int n;
    struct node *next;
};

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

    int n, m, i;

    scanf("%d %d", &n, &m);

    struct node **adj_list = malloc((n + 1) * sizeof(struct node*));

    for (i = 0; i <= n; i++) {
        adj_list[i] = malloc(sizeof(struct node));
        adj_list[i]->n = 0;
        adj_list[i]->next = NULL;
    }

    for(i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        struct node *nod = malloc(sizeof(struct node));
        nod->n = y;
        adj_list[y]->n++;
        nod->next = adj_list[x]->next;
        adj_list[x]->next = nod;
    }

    int q[N], h, t;

    h = t = 0;
    for (i = 1; i <= n; i++) {
        if (adj_list[i]->n == 0) {
            q[t++] = i;
        }
    }

    int nod;
    while (h < t) {
        nod = q[h++];
        printf("%d ", nod);
        struct node* lst = adj_list[nod]->next;
        while(lst != NULL) {
            adj_list[lst->n]->n--;
            if (adj_list[lst->n]->n == 0)
                q[t++] = lst->n;
            lst = lst->next;
        }
    }


    return 0;
}