Cod sursa(job #1566292)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 11 ianuarie 2016 22:56:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
using namespace std;

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

const int dmax = 50000;
const int dim = 100000;

int lst[dmax + 1];
int vf[dim + 1];
int urm[dim + 1];
int nr;

int C[dmax + 1];
int d[dmax + 1];

int N, M;

void adauga(int x, int y)
{
    //ADAUGA IN LISTA LUI x PE y

    nr++;
    vf[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

int main()
{
    int i, x, y, first, last, p;

    in >> N >> M;

    for(i = 1; i <= M; i++)
    {
        in >> x >> y;

        d[y]++;

        adauga(x,y);
    }

    //for(i = 1; i <= N; i++) out << d[i] <<" ";

    first = 1; last = 0;

    //INSEREZ IN COADA NODUTILE i CU d[i] == 0
    for(i = 1; i <= N; i++)
        if(d[i] == 0)
        {
            last++;
            C[last] = i;
        }

    while(first <= last)
    {
        x = C[first];

        //PARCURG LISTA VECINILOR y AI LUI x

        p = lst[x];

        while(p)
        {
            y = vf[p];

            d[y]--;

            if(d[y] == 0)
            {
                last++;
                C[last] = y;
            }

            p = urm[p];
        }

        first++;
    }

    for(i = 1; i <= N; i++) out << C[i] <<" ";

    return 0;
}