Cod sursa(job #2794988)

Utilizator bianca_voicuBianca Voicu bianca_voicu Data 5 noiembrie 2021 20:02:49
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>


using namespace std;

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


class Graph {
private:
    int _n, _m;
    vector<int> _list[100001];

public:
    Graph(int nodes, int edges) : _n(nodes), _m(edges) {}

    void addEdges();

    void SortareTopologica();
};


void Graph::addEdges() {
    int x, y, i;
    for (i = 0; i < _m; i++) {
        f >> x >> y;
        _list[x].push_back(y);
    }
}

//complexitate O(n+m)
void Graph::SortareTopologica() {
    vector<int> grade_interne(_n + 2, 0);
    queue<int> coada;


    //calculez gradele interne ale nodurilor
    for (int i = 1; i <= _n; i++)
        for (int j = 0; j < _list[i].size(); j++)
            grade_interne[_list[i][j]] += 1;

    //adaug in coada toate nodurile cu gradul intern 0
    for (int i = 1; i <= _n; i++)
        if (grade_interne[i] == 0)
            coada.push(i);

    int varf;
    while (!coada.empty()) {
        //extragem un varf din coada
        varf = coada.front();
        g << varf << " ";
        coada.pop();

        //scad gradele interne ale vecinilor, fara sa elimin nodul din reprezentare si adaug in coada vecinii al caror
        // grad intern devine 0
        for (int i = 0; i < _list[varf].size(); i++) {
            grade_interne[_list[varf][i]]--;
            if (grade_interne[_list[varf][i]] == 0)
                coada.push(_list[varf][i]);
        }
    }
}



int main() {
    int n, m;
    f >> n >> m;
    Graph gr(n, m);
    gr.addEdges();

    gr.SortareTopologica();

    f.close();
    g.close();
    return 0;
}