Cod sursa(job #2132376)

Utilizator sulzandreiandrei sulzandrei Data 15 februarie 2018 18:48:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb

#include <fstream>
#include <vector>


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

int main()
{
    int n,m;

    std::vector<int> *Edg;
    in >> n >> m;
    int *Q = new int[n+1];
    int *degi = new int[n+1];
    Edg = new std::vector<int>[n+1];
    int x,y;
    for(int i = 1 ; i<= n ; i++) degi[i] = 0;
    for(int i = 0 ; i <m ; i++)
    {
        in >> x >> y;
        Edg[x].push_back(y);
        degi[y]++;
    }
    int qsize = 0;

    for(int i = 1 ;i <=n ; i++)
        if(degi[i] == 0)
            Q[++qsize] = i;
    for(int i = 1 ; i <=n ; i++)
    {
        x = Q[qsize]; qsize--;
        out<<x<<" ";
        for(int y: Edg[x])
        {
            degi[y]--;
            if(degi[y] == 0)
                Q[++qsize] =y;
        }
    }

    return 0;
}