Pagini recente » Cod sursa (job #2494387) | Cod sursa (job #862603) | Cod sursa (job #1299322) | Cod sursa (job #215581) | Cod sursa (job #2963285)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
constexpr size_t LIM = 5 * 1e4 + 1;
int N, M, node1, node2, indegree[LIM];
vector<int> adj_list[LIM];
bool visited[LIM];
// Algoritmul lui Kahn
static inline vector<int> topological_ordering() {
vector<int> ans;
queue<int> q;
for (int i = 1; i <= N; ++i)
if (!indegree[i]) q.push(i);
while (!q.empty()) {
const int node = q.front();
q.pop();
ans.push_back(node);
for (const int adj : adj_list[node]) {
--indegree[adj];
if (indegree[adj] == 0)
q.push(adj);
}
}
return ans;
}
int main() {
fin >> N >> M;
for (int i = 1; i <= M; ++i) {
fin >> node1 >> node2;
adj_list[node1].push_back(node2);
++indegree[node2];
}
vector<int> ans = topological_ordering();
for (const int node : ans)
fout << node << ' ';
fin.close();
fout.close();
return 0;
}