Cod sursa(job #2276314)

Utilizator ZappaManIosif Adrian-Mihai ZappaMan Data 4 noiembrie 2018 16:25:04
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <list>

using namespace std;

#define MAXN 50005
#define MAXM 100005
#define BLACK 2
#define GRAY 1
#define WHITE 0

using namespace std;

int visited[MAXN];
list<int> ret;
vector<int> g[MAXN];
int N, M;

void dfs(int root) {
   if (visited[root] == BLACK || visited[root] == GRAY) {
      printf("visiting a terminated node, not acyclic!");
      return;
   }

   visited[root] = GRAY;
   for (int n : g[root]) {
      if (visited[n] == WHITE) {
         dfs(n);
      }
   }
   visited[root] = BLACK;
   ret.push_back(root);
}

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 n1, n2;
      scanf("%d %d", &n1, &n2);
      g[n1].push_back(n2);
   }

   for (int i = 1; i <= N; ++i) {
      visited[i] = WHITE;
   }

   for (int i = 1; i <= N; ++i) {
      if (visited[i] == WHITE) {
         dfs(i);
      }
   }

   while (ret.size()) {
      int n = ret.back();
      ret.pop_back();
      printf("%d ", n);
   }

   return 0;
}