Cod sursa(job #2659913)

Utilizator anacomoAna-Maria Comorasu anacomo Data 17 octombrie 2020 19:28:14
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
//todo algoritmul lui Kahn

int main()
{
    int n, m;
    fin >> n >> m;
    
    set <int> fii[n+1];
    vector <int> parinti(n+1);

    for (int i = 0; i < m; ++i)
    {
        int x, y;
        fin >> x >> y;
        if(fii[x].find(y) == fii[x].end())
        {
            fii[x].insert(y);
            parinti[y]++;
        }
    }
    queue <int> parentless;
    for (int i = 1; i <= n; ++i)
    {
        if (parinti[i] == 0)
            parentless.push(i);
    }

    vector <int> sortat;
    while (parentless.empty() == false)
    {
        int nod = parentless.front();
        parentless.pop();
        sortat.push_back(nod);
        for(auto vecin : fii[nod])
        {
            if(--parinti[vecin] == 0)
            {
                fii[nod].erase(vecin);
                parentless.push(vecin);
            }
        }
    }
    

    for(int i = 0; i < sortat.size(); ++i)
    {
        fout << sortat[i] << " ";
    }
    return 0;
}