Cod sursa(job #991214)

Utilizator toranagahVlad Badelita toranagah Data 30 august 2013 00:33:05
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

const int MAX_N = 50100;

int N, M;
vector<int> graph[MAX_N];
bool visited[MAX_N];
vector<int> answer;

void dfs(int node);

int main() {
  fin >> N >> M;
  for (int i = 1, a, b; i <= N; ++i) {
    fin >> a >> b;
    graph[a].push_back(b);
  }

  for (int i = 1; i <= N; ++i) {
    if (!visited[i]) dfs(i);
  }
  
  reverse(answer.begin(), answer.end());
  for (auto x : answer) {
    fout << x << ' ';
  }

  return 0;
}

void dfs(int node) {
  visited[node] = true;

  for (auto x : graph[node]) {
    if (!visited[x]) dfs(x);
  }

  answer.push_back(node);
}