Cod sursa(job #3371756)

Utilizator nstefanNeagu Stefan nstefan Data 31 octombrie 2026 14:17:45
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>
using namespace std;

#ifdef INFOARENA
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
#define cin fin
#define cout fout
#endif

using Graph = vector<vector<int>>;

vector<int> toposort(const Graph& g) {
  // Compute the in-degrees
  vector<int> indeg(g.size());
  for (int node = 1; node < g.size(); node++)
    for (auto neigh : g[node])
      indeg[neigh]++;

  // Push the nodes with in-degree of 1
  vector<int> ans;
  for (int node = 1; node < g.size(); node++)
    if (indeg[node] == 0)
      ans.push_back(node);

  // Toposort the remaining nodes
  for (int i = 0; i < ans.size(); i++)
    for (auto neigh : g[ans[i]])
      if (--indeg[neigh] == 0)
        ans.push_back(neigh);

  return ans;
}

int main() {
  int n, m;
  cin >> n >> m;
  Graph g(n + 1);

  for (int i = 1; i <= m; i++) {
    int from, to; cin >> from >> to;
    g[from].push_back(to);
  }

  auto ans = toposort(g);
  for (auto x : ans)
    cout << x << ' ';
}