Cod sursa(job #2659895)

Utilizator anacomoAna-Maria Comorasu anacomo Data 17 octombrie 2020 18:58:20
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 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];
    set <int> parinti[n+1];

    for (int i = 0; i < m; ++i)
    {
        int x, y;
        fin >> x >> y;
        fii[x].insert(y);
        parinti[y].insert(x);
    }
    queue <int> parentless;
    for (int i = 1; i <= n; ++i)
    {
        if (parinti[i].empty())
            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].size() - 1 == 0)
            {
                fii[nod].erase(vecin);
                parinti[vecin].erase(nod);
                parentless.push(vecin);
            }
        }
    }
    

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