Cod sursa(job #2711417)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 24 februarie 2021 08:06:33
Problema Sortare topologica Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
typedef pair<int,int> pii;
int n,m,grad[50005];
vector<int> sol;
set<int> muchii[50005],in[50005];
set<pii> s;
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a, b;
        fin>>a>>b;
        muchii[a].insert(b);
        in[b].insert(a);
        grad[a]++;
    }
    for(int i=1;i<=n;i++)
        s.insert({grad[i],i});
    while(!s.empty())
    {
        auto it=s.begin();
        int nod=(*it).second;
        sol.push_back(nod);
        for(auto i:in[nod])
        {
            muchii[i].erase(nod);
            s.erase({grad[i],i});
            grad[i]--;
            s.insert({grad[i],i});
        }
        muchii[nod].clear();
        s.erase(it);
    }
    reverse(sol.begin(),sol.end());
    for(int i=0;i<sol.size();i++)
        fout<<sol[i]<<" ";
    return 0;
}