Cod sursa(job #3275157)

Utilizator OanaAOana A OanaA Data 9 februarie 2025 13:13:09
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

int n, m, vizi[10005];
vector <int> graf[10005]; //vecinii nodului i
int grad_intrare[10005];

int main()
{
    cin >>  n >> m;
    for(int i=1; i<=m; ++i)
    {
        int x, y;
        cin >> x >> y;
        graf[x].push_back(y);
        grad_intrare[y]++;
    }

    queue<int> q; // coada cu nodurile cu gr intrare 0
    vector <int> topo_sort; // nodurile sortate

    for(int i=1; i<=n; ++i)
    {
        if(grad_intrare[i] == 0)
            q.push(i);
    }

    while(!q.empty())
    {
        int nod_curent = q.front();
        q.pop();
        topo_sort.push_back(nod_curent);
        for(auto vecin: graf[nod_curent])
        {
            grad_intrare[vecin]--;
            if(grad_intrare[vecin] == 0)
                q.push(vecin);
        }
    }

     for(auto nod: topo_sort)
     {
         cout << nod << " ";
     }
    return 0;
}