Cod sursa(job #872373)

Utilizator Mishu91Andrei Misarca Mishu91 Data 5 februarie 2013 23:32:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int MAX_N = 50005;

vector <int> G[MAX_N];

int N, M;
int InGr[MAX_N];

ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");

void read() {
    fin >> N >> M;

    for (int i = 0; i < M; ++i) {
        int a, b;
        fin >> a >> b;
        G[a].push_back(b);
        ++InGr[b];
    }
}

void solve() {
    queue <int> Q;

    // Push the nodes that have no edge going to them
    for (int i = 1; i <= N; i++) {
        if (InGr[i] == 0) {
            Q.push(i);
        }
    }

    while (!Q.empty()) {
        int current = Q.front();
        Q.pop();

        fout << current << " ";

        for (vector<int>::iterator it = G[current].begin(); it != G[current].end(); ++it) {
            --InGr[*it];

            if (InGr[*it] == 0) {
                Q.push(*it);
            }
        }
    }

    fout << "\n";
}

int main() {
    read();
    solve();
    return 0;
}