Cod sursa(job #2054771)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 2 noiembrie 2017 15:50:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
#define CHECK(x) if(!(x)) return false;

#ifdef INFOARENA
#define ProblemName "sortaret"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

const int MAXN = 50010;
vector<int> G[MAXN];// , rG[MAXN];
int v[MAXN];
int N;
//LL dp[MAXN];
vector<int> toposort;
bool viz[MAXN];

void DFS(int x) {
  viz[x] = true;
  for (const auto &it : G[x])
  if (!viz[it])
    DFS(it);
  toposort.push_back(x);
}

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  int M;
  scanf("%d%d", &N, &M);
  //for (int i = 0; i < N; ++i)
  //  scanf("%d", &v[i]);
  while (M--) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a, --b;
    G[a].push_back(b);
    //rG[b].push_back(a);
  }
  memset(viz, 0, sizeof viz);
  for (int i = 0; i < N; ++i)
  if (!viz[i])
    DFS(i);
  reverse(toposort.begin(), toposort.end());
  //for (const auto &it : topo)
  for (const auto &it : toposort)
    printf("%d ", it + 1);
  puts("");
  return 0;
}