Cod sursa(job #2524241)

Utilizator PushkinPetolea Cosmin Pushkin Data 15 ianuarie 2020 11:36:49
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>
using namespace std;
vector<vector<unsigned short>> G;
vector<unsigned short> d;
unsigned short n;
void rd()
{
    ifstream f("sortaret.in");
    unsigned short x, y;
    f>>n>>x;
    G.resize(n);
    d.resize(n);
    while(f>>x>>y)
    {
        G[x-1].push_back(y-1);
        d[y]++;
    }
    f.close();
}
vector<unsigned short> topsort()
{
    vector<unsigned short> r;
    while(r.size()<n)
    {
        for(unsigned short i=0; i<n; i++)
            if(!d[i])
            {
                r.push_back(i);
                for(auto a:G[i])
                    d[a]--;
                d[i]=USHRT_MAX;
            }
    }
    return r;
}
int main()
{
    rd();
    vector<unsigned short> r=topsort();
    ofstream g("sortaret.out");
    for(auto a:r)
        g<<a<<' ';
    g.close();
    return 0;
}