Cod sursa(job #2256671)

Utilizator ShootingHorseHorsie Horse ShootingHorse Data 8 octombrie 2018 22:14:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
    int id;
    struct node *neighbours;
};

struct node graph[50001];
bool visited[50001];
int sol[50000];
int sol_index;

inline void graph_add_node(int id)
{
    graph[id].id = id;
}

inline void graph_add_arch(int id1, int id2)
{ 
    struct node *node = &(graph[id1]);
    struct node *new_node = NULL;

    new_node = (struct node *)calloc(1, sizeof(struct node *));
    new_node->id = id2;
    new_node->neighbours = node->neighbours;
    node->neighbours = new_node;
}

inline void dfs(int current_node)
{
    struct node *it = graph[current_node].neighbours;

    visited[current_node] = true;
    while(it != NULL) {
        if (!visited[it->id])
            dfs(it->id);

        it = it->neighbours;
    }

    sol[sol_index++] = current_node;
}

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

    int n, m, x, y;
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i++)
        graph_add_node(i);

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

    for (int i = 1; i <= n; i++) {
        if (!visited[i])
            dfs(i);
    }

    for (int i = 0; i < n; i++)
        printf("%d ", sol[--sol_index]);

    return 0;
}