Cod sursa(job #2349951)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 20 februarie 2019 21:22:09
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#include <set>
using namespace std;

#define FILE_NAME "sortaret"
ifstream fin (FILE_NAME".in");
ofstream fout(FILE_NAME".out");

const int MAXN = 50000 + 16;
vector < int > Digraf[MAXN];
set < int > First;
int Deg[MAXN];
int N, M;

int main()
{
    fin >> N >> M;
    while(M--)
    {
        int x, y;
        fin >> x >> y;
        Digraf[x].push_back(y);
        ++Deg[y];
    }

    for(int i = 1; i <= N; ++i)
        if(!Deg[i])
            First.insert(i);

    while(!First.empty())
    {
        int nod = *First.begin();
        fout << nod << ' ';
        First.erase(First.begin());

        while(!Digraf[nod].empty())
        {
            --Deg[Digraf[nod].back()];
            if(!Deg[Digraf[nod].back()])
                First.insert(Digraf[nod].back());
            Digraf[nod].pop_back();
        }
    }

    return 0;
}