Cod sursa(job #2842511)

Utilizator Tudor_IlieIlie Tudor Tudor_Ilie Data 1 februarie 2022 00:01:16
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

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

vector<vector<int>> L;

vector<int>  sort_top;
vector<int>  grade_intrare;

void citire(vector<vector<int>> &L){
    int n,m;
    in>>n>>m;

    L.resize(n+1);


    for(int i=0;i<m;i++){
        int  x,y;
        in>>x>>y;
        L[x].push_back(y);
    }
}

void sorteaza_topologic(vector<vector<int>> &L){

    grade_intrare.resize(L.size(),0);
    for(int i=1;i<L.size();i++){
        for(auto e:L[i]){
            grade_intrare[e]++;
        }
    }
    queue<int> Q;
    for(int i=1;i<grade_intrare.size();i++){
        if(grade_intrare[i]==0){
            Q.push(i);
        }
    }
    while(!Q.empty()){
        int actual = Q.front();
        Q.pop();
        sort_top.push_back(actual);
        for(auto  vecin:L[actual]){
            grade_intrare[vecin]--;
            if(grade_intrare[vecin]==0){
                Q.push(vecin);
            }
        }
    }

}

void afisareL(vector<vector<int>> L){
    int ind=0;
    for(auto i:L){
        cout<<ind++<<" : ";
        for(auto j:i){
            cout<<j<<" ";
        }
        cout<<'\n';
    }
}


int main(){
    citire(L);
    sorteaza_topologic(L);
    for(auto i:sort_top){
        out<<i<<' ';
    }
//    afisareL(L);



}