Cod sursa(job #1810278)

Utilizator stefan_bogdanstefan bogdan stefan_bogdan Data 19 noiembrie 2016 20:38:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <stdio.h>
#include <vector>

#define MAXN 50000 + 10
using namespace std;

FILE *f = fopen("sortaret.in", "r");
FILE *g = fopen("sortaret.out", "w");

vector<int> graph[MAXN];
int n, m, x, y, p;
int used[MAXN], sol[MAXN];

inline void add(int x, int y)
{
    graph[x].push_back(y);
}

inline void read()
{
    fscanf(f, "%d %d", &n, &m);
    for (unsigned int i = 1; i <= m; i++)
        fscanf(f, "%d %d", &x, &y), add(x, y);
}

inline void dfs(int node)
{
    if (used[node] != 0)
        return;
    used[node] = 1;
    for (int i = 0; i < graph[node].size(); i++)
        dfs(graph[node][i]);
    sol[p--] = node;
}

inline void solve()
{
    p = n;
    for (unsigned int i = 1; i <= n; i++)
        dfs(i);
}

inline void write()
{
    for (unsigned int i = 1; i <= n; i++)
        fprintf(g, "%d ", sol[i]);
}

int main()
{
    read();
    solve();
    write();

    fclose(f);
    fclose(g);

    return 0;
}