Cod sursa(job #3204804)

Utilizator Bogdan345Marius Mihalache Bogdan345 Data 17 februarie 2024 14:58:05
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
queue<int>q;
vector<vector<int>>gr;
vector<int>grad_int;
void sortare_topologica(int nod,vector<int>&rasp){
    q.push(nod);
    rasp.push_back(nod);
    while(!q.empty()){
        int nod_curent=q.front();
        q.pop();
        for(auto&x:gr[nod_curent]){
            grad_int[x]--;
            if(grad_int[x]==0){
                rasp.push_back(x);
                q.push(x);
            }
        }
    }

}
int main(){
    int n,m;
    cin>>n>>m;
    gr.resize(n+1);
    grad_int.resize(n+1);
    int a,b;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        gr[a].push_back(b);
        grad_int[b]+=1;
    }
    vector<int>rasp;
    for(int i=1;i<=n;i++){
        if(grad_int[i]==0){
            sortare_topologica(i,rasp);
            break;
        }
    }
    for(auto&x:rasp){
        cout<<x<<" ";
    }
}