Cod sursa(job #2150421)

Utilizator SternulStern Cristian Sternul Data 3 martie 2018 15:48:07
Problema Sortare topologica Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int l[5000][5000], n, m, c[50000], p, u, gin[5000];

void citire()
{
    f>>n>>m;
    for(int q = 1;q <= m;q++)
    {
        int i, j;
        f>>i>>j;
        l[i][0]++;
        l[i][l[i][0]] = j;
        gin[j]++; // gin[j] = 1;
    }
}

void coadez()
{
    p = 1;
    u = 0;
    for(int i = 1;i <= n;i++)
        if(!gin[i])
            c[++u] = i;
}

void extrag()
{
    int i, k;
    while(p<=u)
    {
        i = c[p++];
        for(int j = 1;j <= l[i][0];j++)
            {
                k = l[i][j];
                gin[k] --;
                if(!gin[k])
                    c[++u] = k;
            }
    }
}

void afisez()
{
    for(int i=1;i<=u;i++)
        g<<c[i]<<" ";
}

int main()
{
    citire();
    coadez();
    extrag();
    afisez();
}