Cod sursa(job #2044121)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 20 octombrie 2017 22:08:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

using Graph = vector<vector<int>>;

void dfs(const Graph &graph, vector<bool> &visited, int node, vector<int> &topsort){
  visited[node] = true;

  for (int v: graph[node])
    if (!visited[v])
      dfs(graph, visited, v, topsort);

  topsort.push_back(node);
}

int main(){
  ifstream cin("sortaret.in");
  ofstream cout("sortaret.out");

  ios_base::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;

  Graph graph(N);
  vector<bool> visited(N);
  vector<int> topsort;

  for (int i = 0; i < M; i++){
    int u, v;
    cin >> u >> v;
    u--; v--;

    graph[u].push_back(v);
  }

  for (int i = 0; i < N; i++)
    if (!visited[i])
      dfs(graph, visited, i, topsort);

  for (auto it = topsort.rbegin(); it != topsort.rend(); ++it)
    cout << *it + 1 << " ";
  cout << endl;

  return 0;
}