Cod sursa(job #2196540)

Utilizator cristiancreteanuCristian Creteanu cristiancreteanu Data 19 aprilie 2018 18:10:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

int main() {

    int N, M, i, x, y, node;

//    ifstream f("../input");
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");

    f >> N >> M;
    vector<vector<int>> adj(N + 1);
    vector<int> dgr(N + 1);

    for (i = 1; i <= M; ++i) {
        f >> x >> y;

        adj[x].push_back(y);

        dgr[y]++;
    }

    queue<int> sortT;
    for (i = 1; i <= N; ++i) {
        if (dgr[i] == 0) {
            sortT.push(i);
        }
    }

    vector<int> sol;
    while (!sortT.empty()) {
        node = sortT.front();
        sortT.pop();

        sol.push_back(node);

        for (auto it = adj[node].begin(); it != adj[node].end(); ++it) {
            dgr[*it]--;
            if (dgr[*it] == 0) {
                sortT.push(*it);
            }
        }
    }

    for (auto it = sol.begin(); it != sol.end(); ++it) {
        g << *it << ' ';
    }
    g << '\n';

    g.close();
    f.close();

    return 0;
}