Cod sursa(job #2132336)

Utilizator sulzandreiandrei sulzandrei Data 15 februarie 2018 18:24:09
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb

#include <fstream>
#include <vector>

#include <unordered_set>

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

int main()
{
    int n,m;
    std::unordered_set<int> * To,*Fro;
    std::vector<int> S,L;
    in >> n >> m;
    To = new std::unordered_set<int>[n+1];
    Fro = new std::unordered_set<int>[n+1];
    int x,y;
    for(int i = 0 ; i <m ; i++)
    {
        in >> x >> y;
        To[x].insert(y);
        Fro[y].insert(x);
    }
    for(int i = 1 ; i <= n; i++)
        if(Fro[i].size()==0)
            S.push_back(i);
    while(!S.empty())
    {
        int no = S.back(); S.pop_back();
        L.push_back(no);
        while(To[no].size()!=0)
        {

            int mo = *To[no].begin();
            To[no].erase(mo);
            Fro[mo].erase(no);
            if(Fro[mo].size() == 0)
                S.push_back(mo);
        }
    }
    for(int i: L)
        out<<i<< " ";

    return 0;
}