Cod sursa(job #1657563)

Utilizator msciSergiu Marin msci Data 20 martie 2016 16:40:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <vector>
#include <list>
#include <cstdio>

using namespace std;

const int NMAX = 50005;

vector<int> a[NMAX];
list<int> l;
bool visited[NMAX];
int N, M;

void dfs_visit(int v) {
  visited[v] = true;
  for (auto &i : a[v]) {
    if (!visited[i]) {
      visited[i] = true;
      dfs_visit(i);
    }
  }
  l.push_front(v);
}

void dfs() {
  for (int i = 1; i <= N; i++) {
    visited[i] = false;
  }
  for (int i = 1; i <= N; i++) {
    if (!visited[i]) {
      visited[i] = true;
      dfs_visit(i);
    }
  }
}

int main() {
  freopen("sortaret.in", "r", stdin);
  freopen("sortaret.out", "w", stdout);
  scanf("%d %d", &N, &M);
  for (int i = 0; i < M; i++) {
    int x, y; 
    scanf("%d %d", &x, &y);
    a[x].push_back(y);
  }
  dfs();
  for (auto i : l) {
    printf("%d ", i);
  }
  printf("\n");
  return 0;
}