Cod sursa(job #2026253)

Utilizator AndreiTurcasTurcas Andrei AndreiTurcas Data 24 septembrie 2017 02:34:43
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <set>
#include <stack>
#define removed -999999999
using namespace std;

int n, m, degex[50002];
stack <int> S;
set <int> G[50002];

void clean(int x)
{
    for(set <int> :: iterator it = G[x].begin(); it != G[x].end(); ++it)
        degex[*it]--;
}

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    cin >> n >> m;
    for(; m; --m)
    {
        int x, y;
        cin >> x >> y;
        G[y].insert(x);
        ++degex[x];
    }
    int nr = 0;
    while(nr != n)
    {
        for(int i = 1; i <= n; ++i)
        if(!degex[i])
        {
            S.push(i);
            degex[i] = removed;
            clean(i);
            ++nr;
        }
    }
    while(!S.empty())
    {
        cout << S.top() << " ";
        S.pop();
    }
}