Pagini recente » Cod sursa (job #1490718) | Cod sursa (job #409443) | Cod sursa (job #1334870) | Cod sursa (job #1884315) | Cod sursa (job #3271545)
#include <bits/stdc++.h>
using namespace std;
vector <int> graph[100005]; // graph[i] = este un vector <int> care retine toti vecinii nodului i
int gradIntrare[100005]; // gradIntrare[i] = retine gradul de intrare al nodului i
int main() {
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
graph[x].push_back(y); // deoarece este graph orientat, pushez doar pe y in lista de vecini ai lui x
gradIntrare[y]++; // crestem gradul de intrare al lui y
}
queue <int> q; // o coada care contine nodurile cu grad de intrare 0 la momentul actual
vector <int> topoSort; // va contine nodurile in ordinea sortata
for (int i = 1; i <= n; i++) {
if (gradIntrare[i] == 0) {
q.push(i); // mai intai populam coada cu toate gradele de intrare 0
}
}
while (!q.empty()) {
int node = q.front(); // cat timp coada este goala, o sa imi iau un nod din ea - despre care stim ca are
// grad de intrare 0
q.pop(); // il scoatem din coada pentru ca nu o sa mai avem nevoie de el odata ce l am procesat
topoSort.push_back(node); // deoarece are grad de intrare 0, il pot insera in sortarea topologica
for (auto neighbor : graph[node]) {
// trebuie sa scad gradul de intrare al fiecarui vecin al lui node cu 1
gradIntrare[neighbor]--;
// daca vecinul a ajuns la grad de intrare 0, trebuie sa il inserez in coada pentru a fi procesat uterior
if (gradIntrare[neighbor] == 0) {
q.push(neighbor);
}
}
}
// afisez sortarea topologica
for (auto node : topoSort) {
cout << node << " ";
}
}