Cod sursa(job #3351628)

Utilizator bobertbobert bobert Data 20 aprilie 2026 17:23:15
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb
#include <bits/stdc++.h>
using namespace std;

unordered_map<int, vector<int>> graph;

int main(void)
{
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    unsigned int n, m;
    fin >> n >> m;

    int x, y;

    vector<int> in_degree(n + 1, 0);
    
    for (int i = 0; i < m; i++) {
        fin >> x >> y;
        graph[x].push_back(y);
        in_degree[y]++;
    }

    queue<int> bfs_queue;

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

    /**
     * se porneste parcurgerea BFS
        la fiecare pas se vizitează un nod node
        se șterg toate muchiile care pleacă din node: (node,neigh)
        neigh
        este adaugat in coada doar daca devine un nod cu grad intern 0
        se verifica la finalul parcugerii daca mai sunt muchii ramase in graf
        daca inca mai exista muchii neșterse, atunci graful conține cel puțin un ciclu - nu se poate determina o sortare topologică
        altfel, ordinea in care s-au scos nodurile din coada reprezinta o sortare topologica

        pentru a evita ștergerea propriu-zisă a muchiilor din graf, se poate modifica gradul intern al fiecărui nod (care poate fi reținut într-un vector in_degree[node]
     */
    while (!bfs_queue.empty()) {
        int node = bfs_queue.front();
        bfs_queue.pop();
        // ordinea in care s-au scos nodurile din coada reprezinta o sortare topologica
        fout << node << " ";
        
        for (int neigh : graph[node]) {
            in_degree[neigh]--;
            if (in_degree[neigh] == 0) {
                bfs_queue.push(neigh);
            }
        }
    }

    /**
     * se verifica la finalul parcugerii daca mai sunt muchii ramase in graf
        daca inca mai exista muchii neșterse, atunci graful conține cel puțin un ciclu - nu se poate determina o sortare topologică
        altfel, ordinea in care s-au scos nodurile din coada reprezinta o sortare topologica
     */
        // for (int i = 1; i <= n; i++) {
        //     if (in_degree[i] > 0) {
        //         fout << "Nu se poate determina o sortare topologica";
        //         return 0;
        //     }
        // }


    return 0;
}