Cod sursa(job #2476539)

Utilizator PatrascuAdrian1Patrascu Adrian Octavian PatrascuAdrian1 Data 19 octombrie 2019 08:36:37
Problema Sortare topologica Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <set>
#include <queue>

using namespace std;

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

const int Nmax = 5e4 + 5;
set <int> a[Nmax];
set <int>::iterator it;
int q[Nmax];
int g[Nmax];
int N,M;

int main()
{
    in >> N >> M;
    while(M--)
    {
        int x,y;
        in >> x >> y;
        a[x].insert(y);
        g[y]++;
    }
    for(int i = 1; i <= N; ++i)
        if(!g[i])
            q[++q[0]] = i;
    for(int i = 1; i <= N; ++i)
    {
        int x = q[i];
        for(it = a[x].begin(); it != a[x].end(); ++it)
        {
            g[*it]--;
            if(!g[*it])
                q[++q[0]] = *it;
        }
    }
    for(int i = 1; i <= N; ++i)
        out << q[i] << " ";

    return 0;
}