Cod sursa(job #3371713)

Utilizator nstefanNeagu Stefan nstefan Data 31 octombrie 2026 13:05:54
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
#include <algorithm>
#include <deque>
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) {
  vector<int> ans;

  vector<int> indeg(g.size());
  for (int i = 1; i < g.size(); i++)
    for (auto neigh : g[i])
      indeg[neigh]++;

  deque<int> dq;
  for (int node = 1; node < g.size(); node++)
    if (indeg[node] == 0)
      dq.push_back(node);

  while (!dq.empty()) {
    int node = dq.front();
    dq.pop_front();

    ans.push_back(node);

    for (auto neigh : g[node]) {
      if (indeg[neigh] == 0) continue;
      if (--indeg[neigh] == 0)
        dq.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 << ' ';
}