Pagini recente » Cod sursa (job #349361) | Cod sursa (job #3264394) | Cod sursa (job #3261971) | Cod sursa (job #2514492) | Cod sursa (job #2667905)
#include <bits/stdc++.h>
using namespace std;
struct Graph {
int n;
vector<vector<int>> adj;
Graph(int n_verts) :
n(n_verts), adj(n_verts) {}
vector<int> TopSort() {
vector<int> in_degree(n, 0);
for (int from = 0; from < n; from++) {
for (int to : adj[from]) {
in_degree[to]++;
}
}
vector<int> q;
for (int node = 0; node < n; node++) {
if (in_degree[node] == 0) {
q.push_back(node);
}
}
for (int i = 0; i < (int)q.size(); i++) {
int node = q[i];
for (int neighbor : adj[node]) {
in_degree[neighbor]--;
if (in_degree[neighbor] == 0) {
q.push_back(neighbor);
}
}
}
// if ((int)q.size() < n)
// return {};
return q;
}
void AddEdge(int a, int b) {
adj[a].push_back(b);
}
};
int main() {
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n, m;
fin >> n >> m;
Graph graph(n);
for (int i = 0; i < m; i++) {
int x, y;
fin >> x >> y;
graph.AddEdge(x - 1, y - 1);
}
vector<int> topsort = graph.TopSort();
for (int node : topsort) {
fout << node + 1 << " ";
}
fout << '\n';
return 0;
}