Cod sursa(job #1413773)

Utilizator PureGPureGains PureG Data 2 aprilie 2015 08:27:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
/*
    Keep It Simple!
*/

#include <vector>
#include <fstream>
#include <queue>

using namespace std;

const int kMaxN = 50005;

int N,M;
vector<int> G[kMaxN],topo;
int deg[kMaxN];
queue<int> que;

void Solve() {
    ifstream fin("sortaret.in");
    fin >> N >> M;
    for (int i(1); i <= M; ++i) {
        int x,y;
        fin >> x >> y;
        G[x].push_back(y);
        ++deg[y];
    }
    fin.close();
    for (int i(1); i<= N; ++i)
        if (!deg[i])
            que.push(i);
    while (!que.empty()) {
        int node = que.front();
        que.pop();
        topo.push_back(node);
        for (auto it : G[node]) {
            --deg[it];
            if (!deg[it])
                que.push(it);
        }
    }
    ofstream fout("sortaret.out");
    for (auto it:topo)
        fout << it << ' ';
    fout << '\n';
    fout.close();
}

int main() {
    Solve();
    return 0;
}