Cod sursa(job #3335153)

Utilizator StefanL2005Stefan Leustean StefanL2005 Data 21 ianuarie 2026 19:03:03
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
ifstream in ("sortaret.in");
ofstream out ("sortaret.out");

vector<int> SortareTopologicaGRAD(int n, vector<vector<int>> &vecini)
{
    vector<int> dgrad(n, 0);
    vector<int> ans;
    queue<int> Q;

    for (int i = 0; i < n; i++)
        for (int v : vecini[i])
            dgrad[v]++;
    for (int i = 0; i < n; i++)
        if (dgrad[i] == 0)
            Q.push(i);

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

        ans.push_back(nod);

        for (int v : vecini[nod])
        {
            dgrad[v]--;
            if (dgrad[v] == 0)
                Q.push(v);
        }
    }

    return ans;
}

int main()
{
    int n, m; in >> n >> m;
    vector<vector<int>> vecini(n);

    for (int i = 0; i < m; i++)
    {
        int x, y; in >> x >> y;
        x--; y--;
        vecini[x].push_back(y);
    }

    vector<int> sortTop = SortareTopologicaGRAD(n, vecini);

    //cout << "SorateTopologicaGRAD: ";
    for (auto i : sortTop)
        out << i++ << " ";
    out << "\n";
    return 0;
}