Cod sursa(job #1657556)

Utilizator msciSergiu Marin msci Data 20 martie 2016 16:30:57
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>
#include <list>

using namespace std;

const int NMAX = 50005;

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

void dfs_visit(int v) {
  for (int i = 1; i <= N; i++) {
    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 = 1; i <= M; i++) {
    int x, y; scanf("%d %d", &x, &y);
    a[x][y] = 1;
  }
  dfs();
  for (auto i : l) {
    printf("%d ", i);
  }
}