Cod sursa(job #3335608)

Utilizator RalucaioneteRalucaIonete Ralucaionete Data 23 ianuarie 2026 01:32:37
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int N = 5e4;
vector<int> lista_ad[N + 1];
queue<int> bfs;
int grade_in[N + 1], vizitat[N + 1];

int main()
{
    int n, m, topo_cnt = 0;
    in >> n >> m;
    int topo_sort[n];

    int u, v;
    for (int i = 0; i < m; i++)
    {
        in >> u >> v;
        lista_ad[u].push_back(v);
        grade_in[v]++;
    }

    int start;
    for (int i = 1; i <= n; i++)
    {
        if (grade_in[i] == 0)
        {
            // am gasit primul nod de grad 0 din graf si incepem parcurgerea bfs din el
            start = i;
            vizitat[start] = true;
            bfs.push(start);
        }
        else
        {
            vizitat[i] = false;
        }
    }

    while (!bfs.empty())
    {
        int curent = bfs.front();

        for (int v : lista_ad[curent])
        {
            // pentru fiecare nod adiacent al nodului cu grad in = 0, scadem gradul nodului adiacent cu 1
            grade_in[v]--;
            vizitat[v] = true;
            if (grade_in[v] == 0)
                bfs.push(v);
        }
        topo_sort[topo_cnt] = curent;
        topo_cnt++;
        bfs.pop();
    }

    for (int x : topo_sort)
        out << x << " ";
    return 0;
}