Cod sursa(job #2926303)

Utilizator iulia.talpalariuIulia-Georgiana Talpalariu iulia.talpalariu Data 17 octombrie 2022 17:39:27
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <vector>
#include <queue>
#include <fstream>
#include <iostream>
using namespace std;
ifstream fileIn("sortaret.in");
ofstream fileOut("sortaret.out");

class Graph {
    int N;
    int M;
    vector<vector<int>> list_ad;
    vector<int> degree;

    public:
        void read();
        vector<int> topological_sort();


};

void Graph:: read() {
    fileIn >> N >> M;
    // resize
    list_ad.resize(N+1);
    degree.resize(N+1, 0);

    int a, b;
    for(int i=0; i<= M-1; i++) {
            fileIn >> a >> b;
            list_ad[a].push_back(b);
            degree[b]++;
    }

}

vector<int> Graph::topological_sort() {
    queue<int> C;
    vector<int> sorted;
    for(int i = 1; i<= N; i++){
        if(degree[i] == 0) {
            C.push(i);
        }
    }
    int elem;
    while(!C.empty()) {
        elem = C.front();
        C.pop();
        sorted.push_back(elem);
        for(auto neib: list_ad[elem]) {
            degree[neib]--;
            if (degree[neib] == 0) {
                C.push(neib);
            }
        }
    }
    return sorted;
}


int main() {
    Graph my_graph;
    my_graph.read();
    vector<int> sortare = my_graph.topological_sort();
    for(auto k : sortare) {
        cout << k <<" ";
    }


return 0;
}