Pagini recente » Cod sursa (job #2097997) | Cod sursa (job #3355076) | Cod sursa (job #1735256) | Cod sursa (job #1649080) | Cod sursa (job #3322138)
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int> > adj_list;
vector<int> in_degree;
int N;
void read_input() {
ifstream input("sortaret.in");
int M;
input >> N >> M;
adj_list.resize(N + 1);
in_degree.resize(N + 1);
for (int i = 0; i < M; i++) {
int u, v;
input >> u >> v;
if (find(adj_list[u].begin(), adj_list[u].end(), v) != adj_list[u].end())
continue; // ignore duplicate edges
adj_list[u].push_back(v);
}
}
vector<int> topo_sort() {
vector<int> topo_list;
queue <int> free_nodes;
for (int i = 1; i <= N; i++)
if (in_degree[i] == 0)
free_nodes.push(i);
while (!free_nodes.empty()) {
int u = free_nodes.front(); free_nodes.pop();
topo_list.push_back(u);
for (int neigh : adj_list[u]) {
in_degree[neigh]--;
if (in_degree[neigh] == 0)
free_nodes.push(neigh);
}
}
return topo_list;
}
int main() {
read_input();
vector<int> topo_list = topo_sort();
ofstream output("sortaret.out");
for (int u: topo_list)
output << u << " ";
return 0;
}