Course Schedule

#include <bits/stdc++.h>
using namespace std;
 
#define PRINT_ARR(arr, n)                                                      \
  do {                                                                         \
    for (int i = 0; i < n; i++) {                                              \
      cout << arr[i] << " ";                                                   \
    }                                                                          \
    cout << "\n";                                                              \
  } while (0)
#define N (int)1e6
 
typedef long long ll;
enum color_t { WHITE, GRAY, BLACK, COLOR_SIZE };
 
color_t visited[N];
 
int get_new_node(int n) {
  static int i = 1;
  for (; i <= n; i++)
    if (visited[i] == WHITE)
      return i;
  return -1;
}
 
bool dfs(const vector<int> *v, const int n, const int i, vector<int> &ord) {
  (void)n;
  if (visited[i] == BLACK)
    return true;
  if (visited[i] == GRAY)
    return false;
 
  visited[i] = GRAY;
  for (auto node : v[i]) {
    if (!dfs(v, n, node, ord))
      return false;
  }
  visited[i] = BLACK;
  ord.push_back(i);
  return true;
}
 
bool solve(const vector<int> *v, vector<int> &ord, const int n) {
  int i;
  while ((i = get_new_node(n)) != -1) {
    if (!dfs(v, n, i, ord)) {
      return false;
    }
  }
  return true;
}
 
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
 
  int n, m;
  cin >> n >> m;
  vector<int> v[n + 1];
  vector<int> ord;
 
  int a, b;
  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    v[a].push_back(b);
  }
 
  if (!solve(v, ord, n)) {
    cout << "IMPOSSIBLE" << endl;
  } else {
    reverse(ord.begin(), ord.end());
    for (auto i : ord) {
      cout << i << " ";
    }
    cout << endl;
  }
 
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED