Cod sursa(job #1254021)

Utilizator andreiagAndrei Galusca andreiag Data 2 noiembrie 2014 02:42:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;
const int Nmax = 50055;

vector<int> G[Nmax];
int deg[Nmax], sol[Nmax];

int main()
{
    ifstream f ("sortaret.in");
    ofstream g ("sortaret.out");
    
    int N, M, a, b;
    f >> N >> M;
    for (int i = 0; i < M; i++)
    {
        f >> a >> b;
        G[b].push_back(a);
        deg[a]++;
    }
    
    queue<int> Q;
    for (int i = 1; i <= N; i++)
        if (deg[i] == 0)
            Q.push(i);
    
    while (!Q.empty()) {
        int v = Q.front();
        Q.pop();
        sol[++sol[0]] = v;
        for (auto a: G[v]) {
            deg[a]--;
            if (deg[a] == 0)
                Q.push(a);
        }
    }
    
    for (int i = N; i > 0; i--) {
        g << sol[i] << ' ';
    }
    g << '\n';
    
    return 0;
}