Cod sursa(job #2150820)

Utilizator SternulStern Cristian Sternul Data 3 martie 2018 19:58:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#define NMAX 50100
using namespace std;

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

int n, m, Q[NMAX], Gin[NMAX], u, p;
vector <int> G[NMAX];

void citire()
{
    int i, j;
    f>>n>>m;
    for(int q = 1;q <= m; q++)
    {
        f>>i>>j;
        G[i].push_back(j);
        Gin[j]++;
    }
}

void coadare()
{
    p = 1;
    u = 0;
    for(int i = 1;i <= n;i++)
        if(!Gin[i])
            Q[++u] = i;
}

void solve()
{
    int i, x;
    vector<int>:: iterator it;
    while(p<=u)
    {
        x = Q[p++];
        for(it = G[x].begin();it != G[x].end();it++)
        {
            Gin[*it]--;
            if(!Gin[*it])
                Q[++u] = *it;
        }
    }
}

void afisare()
{
    for(int i=1;i<=n;i++)
        g<<Q[i]<<" ";
}
int main()
{
    citire();
    coadare();
    solve();
    afisare();
}