Cod sursa(job #3371611)

Utilizator nstefanNeagu Stefan nstefan Data 31 octombrie 2026 03:48:56
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
using namespace std;

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

using Graph = vector<vector<int>>;

vector<int> toposort(const Graph& g) {
  vector<int> visited(g.size());
  auto dfs = [&](auto self, int node, vector<int>& out) {
    if (visited[node]) return;
    visited[node] = 1;

    for (auto neigh : g[node])
      if (!visited[neigh])
        self(self, node, out);
    
    out.push_back(node);
  };

  vector<int> ans;
  for (int i = 1; i < g.size(); i++)
    if (!visited[i])
      dfs(dfs, i, ans);

  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 << ' ';
}