Cod sursa(job #2211240)

Utilizator MateiTrandafirMatei Trandafir MateiTrandafir Data 9 iunie 2018 16:57:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#define N 50001
#define M 100001

int start[N], value[M], next[M], count, nrd[N];

inline int add(int from, int to) {
    ++count;
    value[count] = to;
    next[count] = start[from];
    start[from] = count;
}

int q[N], st, dr = -1;

void bfs(int x) {
    int y;
    for (int p = start[x]; p != 0; p = next[p]) {
        y = value[p];
        --nrd[y];
        if (nrd[y] == 0) q[++dr] = y;
    }
}

int main() {
    std::ifstream in("sortaret.in");
    std::ofstream out("sortaret.out");
    int i, n, m, x, y;
    in >> n >> m;
    for (i = 0; i < m; ++i) {
        in >> x >> y;
        add(x, y);
        ++nrd[y];
    }
    for (i = 1; i <= n; ++i) if (nrd[i] == 0) q[++dr] = i;
    while (st <= dr) {
        out << q[st] << ' ';
        bfs(q[st]);
        ++st;
    }
    return 0;
}