Pagini recente » Cod sursa (job #2031697) | Cod sursa (job #285203) | Cod sursa (job #182459) | Cod sursa (job #800969) | Cod sursa (job #2794988)
#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;
}