Cod sursa(job #3269818)

Utilizator stefan0211Tacu Darius Stefan stefan0211 Data 20 ianuarie 2025 21:45:41
Problema Sortare topologica Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n, m;
vector<set<int>> la;
vector<int> sortare_topologica, grad_intern;

void Read()
{
    f >> n >> m;

    la.resize(n + 1);
    grad_intern.resize(n + 1, 0);

    for (int i = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        la[x].insert(y);
        grad_intern[y]++;
    }
}

void sorteaza_topoligic(vector<set<int>> &la, vector<int> &sortare_topologica, vector<int> &grad_intern)
{
    queue<int> coada;
    for (int i = 1; i <= n; i++)
        if (grad_intern[i] == 0)
            coada.push(i);

    while (!coada.empty())
    {
        int nod = coada.front();
        coada.pop();

        for (auto &vecin : la[nod])
        {
            grad_intern[vecin]--;
            if (grad_intern[vecin] == 0)
                coada.push(vecin);
        }

        sortare_topologica.push_back(nod);
    }
}

int main()
{
    Read();

    sorteaza_topoligic(la, sortare_topologica, grad_intern);

    for (auto &nod : sortare_topologica)
    {
        g << nod << ' ';
    }

    return 0;
}