Cod sursa(job #1889414)

Utilizator dan.marculetFII MarculetDan dan.marculet Data 22 februarie 2017 18:34:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <cstdio>
#include <vector>
#include <unordered_set>
#include <list>
using namespace std;

auto fin = fopen("sortaret.in", "r");
auto fout = fopen("sortaret.out", "w");

unsigned int n, m;
vector<vector<unsigned int>> a;
vector<unsigned int> deg;
list<int> res;

void input() {
    vector<unordered_set<int>> mark;
    fscanf(fin, "%d %d", &n, &m);
    a.resize(n);
    deg.resize(n);
    mark.resize(n);
    for (auto i = 0u; i < m; ++i) {
        int x, y;
        fscanf(fin, "%d %d", &x, &y);
        --x; --y;
        if (mark[x].find(y) != mark[x].end())
            continue;
        a[x].push_back(y);
        mark[x].insert(y);
        ++deg[y];
    }
}

void solve() {
    vector<int> s;
    for (auto i = 0u; i < n; ++i)
        if (deg[i] == 0)
            s.push_back(i);
    while (s.size()) {
        auto node = s.back();
        s.pop_back();
        res.push_back(node);
        for (auto i = a[node].begin(); i != a[node].end(); ++i) {
            --deg[*i];
            if (deg[*i] == 0)
                s.push_back(*i);
        }
    }
}

void output() {
    for (auto i = res.cbegin(); i !=res.cend(); ++i)
        fprintf(fout, "%d ", *i + 1);
}

void debug() {
    for (auto i = 0u; i < n; ++i) {
        printf("%2d: ", i);
        for (auto j = 0u; j < a[i].size(); ++j)
            printf("%d ", a[i][j]);
        printf("\n");
    }
}

int main() {
    input();
    // debug();
    solve();
    output();

    return 0;
}