Cod sursa(job #795752)

Utilizator dumitru.cearaDumitru Ceara dumitru.ceara Data 9 octombrie 2012 15:55:39
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.56 kb
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define MAX_N 50000
#define MAX_M 100000

typedef struct edge {
    int x;
    int y;
    struct edge* next;
} edge_t;

typedef enum color {
    WHITE,
    GRAY,
    BLACK
} color_t;

typedef struct node {
    edge_t* edges;
    color_t col;
} node_t;

void add_edge(node_t* g, int x, int y)
{
    edge_t* e = malloc(sizeof(*e));
    e->x = x;
    e->y = y;
    e->next = g[x].edges;
    g[x].edges = e;
}

void dfs(node_t* g, int node, void (*f)(int node))
{
    node_t* n = &g[node];
    edge_t* e;

    assert(n->col == WHITE);
    n->col = GRAY;
    for (e = n->edges; e; e = e->next) {
        if (g[e->y].col == WHITE) {
            dfs(g, e->y, f);
        }
    }
    n->col = BLACK;
    f(node);
}

void init(const char* input, const char* output)
{
    freopen(input, "r", stdin);
    freopen(output, "w", stdout);
}

node_t graph[MAX_N + 1];
int n;
int g_tsort[MAX_N];
int g_tsort_cnt = 0;

void topo_sort_cb(int node)
{
    g_tsort[g_tsort_cnt++] = node;
} 

void topo_sort(node_t* g, int n)
{
    int i;
    for (i = 1; i <= n; i++) {
        if (g[i].col == WHITE)
            dfs(g, i, topo_sort_cb);
    }
}

void read()
{
    int i, m;

    scanf("%d", &n);
    scanf("%d", &m);
    for (i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        add_edge(graph, x, y);
    }
}

void write()
{
    int i;
    for (i = g_tsort_cnt - 1; i >= 0; i--) printf("%d ", g_tsort[i]);
}

int main()
{
    init("sortaret.in", "sortaret.out");
    read();
    topo_sort(graph, n);
    write();
    return 0;
}