Cod sursa(job #1520956)

Utilizator BaweeLazar Vlad Bawee Data 9 noiembrie 2015 19:29:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>

using namespace std;

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

struct Nod
{
    int nod,cost;
    Nod *urm;
};
typedef Nod *PNod;

PNod L[50001],p;
int grade[50001],n,m,in,sf,u;
int q[2 * 50001];

void add(int x, int y)
{
    PNod p = new Nod;
    p -> nod = y;
    p -> urm = L[x];
    L[x] = p;

    grade[y]++;
}

int main()
{
    int x,y;

    f >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        f >> x >> y;
        add(x,y);
    }

    for(int i = 1; i <= n; i++)
        if(!grade[i])
            q[++sf] = i;

    in = 1;
    while(in <= sf)
    {
        u = q[in];
        for(p = L[u]; p; p = p -> urm)
        {
            grade[p -> nod]--;
            if(!grade[p -> nod])
                q[++sf] = p -> nod;
        }
        g << u << " ";
        in++;
    }
    return 0;
}