Cod sursa(job #2926305)

Utilizator ralucarRogoza Raluca ralucar Data 17 octombrie 2022 17:41:00
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n,m,x,y;
vector<vector<int>>lista_adiacenta(10001);
vector <int> grad(10001,0);
vector <int> sortare;
queue <int> coada;

void sortare_topologica(){
    for(int i=1; i<=n; i++){
        if(grad[i]==0){
            coada.push(i);
            //cout<<i<<endl;
        }

    }
    while(!coada.empty()){
        int nod=coada.front();
        coada.pop();
        sortare.push_back(nod);
        for(auto j:lista_adiacenta[nod]){
            grad[j]--;
            if(grad[j]==0)
                coada.push(j);
        }
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++){
        fin>>x>>y;
        lista_adiacenta[x].push_back(y);
        grad[y]++;
    }
//    for(int i=1; i<=n;i++){
//        cout<<grad[i]<<" ";
//    }
//    cout<<endl;
    sortare_topologica();
    for(auto i:sortare){
        fout<<i<<" ";
    }
    return 0;
}