Cod sursa(job #1438861)

Utilizator RazvanSSavu Razvan RazvanS Data 21 mai 2015 00:15:21
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.46 kb
/* 
 * File:   main.c
 * Author: Razvan
 *
 * Created on May 19, 2015, 7:50 AM
 */

#include <stdio.h>
#include <stdlib.h>

#define FILE_IN "sortaret.in"
#define FILE_OUT "sortaret.out"

typedef struct list
{
    unsigned int node;
    struct list * next;
} List, *pList;

unsigned n, m, i, x, y;
pList*  neigh;
pList rez;
unsigned * viz;

void addNeigh(unsigned x, unsigned y)
{
    pList new_node = (pList) malloc (sizeof(List));
    new_node->node = y;
    new_node->next = neigh[x];
    neigh[x] = new_node;
}

void addToRez(unsigned node)
{
    pList new_node = (pList) malloc (sizeof(List));
    new_node->node = node;
    new_node->next = rez;
    rez = new_node;
}

void deep(unsigned node)
{
    viz[node] = 1;
    pList child = neigh[node];
    while (child)
    {
        if (!viz[child->node])
            deep(child->node);
        child = child->next;
    }
    addToRez(node);
}

/*
 * 
 */
int main(int argc, char** argv) {
    freopen(FILE_IN, "r", stdin);
    freopen(FILE_OUT, "w", stdout);
    scanf("%d %d", &n, &m);
    neigh = (pList*) calloc (n+1, sizeof(pList));
    for(i=0;i<m;++i)
    {
        scanf("%d %d", &x, &y);
        addNeigh(x, y);
    }
    viz = (unsigned *) calloc (n+1, sizeof(unsigned));
    for(i=1;i<=n;++i)
        if (!viz[i])
            deep(i);
    while(rez)
    {
        printf("%u ", rez->node);
        rez = rez->next;       
    }
    return (EXIT_SUCCESS);
}