Pagini recente » Cod sursa (job #3245207) | Cod sursa (job #2875022) | Cod sursa (job #341554) | Cod sursa (job #996264) | Cod sursa (job #3295256)
#include <cstdio>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
vector<int> TopoSort(vector<vector<int>> adj, int N) {
// vector to store the indegree
vector<int> indegree(N);
for(int i = 1; i <= N; i++) {
for(int x : adj[i]) {
indegree[x]++;
}
}
// queue to store the verticles with indegree 0
queue<int> q;
for (int i = 1; i <= N; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
vector<int> res;
while(!q.empty()) {
int crt = q.front();
q.pop();
res.push_back(crt);
// decrese the indegree
for(int i : adj[crt]) {
indegree[i]--;
// if it has indegree 0 now push it to the queue
if(indegree[i] == 0)
q.push(i);
}
}
if (res.size() != N) {
cout << "Graph contains cycle!" << endl;
return {};
}
return res;
}
int main() {
// sortarea topologica a varfurilor unui graf
// folosind Kahn sau BFS
// adaugam toate nodurile cu indegree 0 in coada
// cat timp coada nu este goala scoatem un nod din coadad si decrementam indegree pt nodul dest cu 1
// daca devine 0 il bag in coada
// daca coada e goala si inca sunt noduri in graf, graful este ciclic si nu poate fii sortat topo
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
int N, M;
cin >> N >> M;
vector<vector<int>> adj(N+1);
for(int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
}
vector<int> res = TopoSort(adj, N);
for (int i = 0; i < N; i ++) {
cout << res[i] << " ";
}
return 0;
}