Pagini recente » Cod sursa (job #2605270) | Cod sursa (job #2420438) | Cod sursa (job #2538353) | Cod sursa (job #1527083) | Cod sursa (job #2313260)
/* Kahn's algorithm for finding the topological order
--------------------------------------------------
- topological order is only possible for DAG
- there can be more then one topological ordering
This approach is based on the following fact
---------------------------------------------
- a DAG has at least one vertex with in-degree 0 and one vertex with out-degree 0
*/
#include <bits/stdc++.h>
using namespace std;
FILE *fin = freopen("sortaret.in", "r", stdin);
FILE *fout = freopen("sortaret.out", "w", stdout);
const int nmax = 5e4+3;
struct Graph {
int nodes;
vector <vector<int>> adj;
Graph(int n) : nodes(n), adj(n+1) { }
void add_edge(int from, int to) {
adj[from].push_back(to);
}
};
queue <int> q;
vector <int> topological_sort(Graph g) {
vector <int> degree(g.nodes+1);
vector <int> order;
for (int from = 1; from <= g.nodes; ++ from)
for (int to : g.adj[from])
degree[to] ++;
for (int node = 1; node <= g.nodes; ++ node)
if (degree[node] == 0)
q.push(node);
while (! q.empty()) {
int u = q.front();
order.push_back(u);
q.pop();
for (int v : g.adj[u])
if(!--degree[v])
q.push(v);
}
return order;
}
int main() {
int n, m;
cin >> n >> m;
Graph g(n);
for (; m > 0; -- m) {
int from, to;
cin >> from >> to;
g.add_edge(from, to);
}
vector <int> order = topological_sort(g);
for (int node : order)
cout << node << " ";
return 0;
}