Cod sursa(job #3371614)

Utilizator nstefanNeagu Stefan nstefan Data 31 octombrie 2026 03:54:40
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
#include <algorithm>
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> visited(g.size());

  auto dfs = [&](auto self, int node, vector<int>& out) {
    // Step 1: mark as visited
    if (visited[node]) return;
    visited[node] = 1;


    // Step 3: ⚠️ Important ⚠️ mark the node
    out.push_back(node);

    // Step 2: propagate the dfs
    for (auto neigh : g[node])
      if (!visited[neigh])
        self(self, neigh, out);
  };

  // Run the dfs for every unmarked node
  vector<int> ans;
  for (int i = 1; i < g.size(); i++)
    if (!visited[i])
      dfs(dfs, i, ans);

  // Reverse to get the actual topological sort
  // reverse(ans.begin(), ans.end());
  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 << ' ';
}