Course Schedule

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>

using namespace std;

using ll  = long long;

using vi  = vector<int>;
using vc = vector<char>;
using vll = vector<long long>;
using vs  = vector<string>;
using vb = vector<bool>;
using vvi  = vector<vector<int>>;
using vvll = vector<vector<long long>>;
using vvc  = vector<vector<char>>;
using vvb  = vector<vector<bool>>;
using vvpll = vector<vector<pair<ll,ll>>>;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

using pq_ll = priority_queue<ll>;
using pq_pll = priority_queue<pll>;
using pq_pll_g = priority_queue<pll, vector<pll>, greater<pll>>;


#define all(x) (x).begin(), (x).end()
#define pb push_back
#define sz(x) ((int)(x).size())
#define forn(i, n) for (int i = 0; i < (n); ++i)
#define fore(i, ini, n) for (int i = ini; i < (n); ++i)
#define forr(i, ini, end) for (int i = ini; i >= end; --i)


int n, m, x, q;
const ll INF = 1e18;
const int MODULO = 1e9 + 7;

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
char dir[] = {'U', 'D', 'L', 'R'};
bool pos_ok(int a, int b){
  return a >= 0 and a < n and b >= 0 and b < m;
}

bool dfs(const vvll& adj, vll& state, vll& topo, ll node){
  state[node] = 1;

  for(const auto& nei: adj[node]){
    if(state[nei] == 2) continue;
    if(state[nei] == 1 || !dfs(adj, state, topo, nei)) return false;
  }

  state[node] = 2;
  topo.pb(node);
  return true;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n >> m;

  vvll adj(n+1);

  ll a, b;
  forn(i, m){
    cin >> a >> b;
    adj[a].pb(b);
  }

  vll state(n+1, 0);
  vll topo;

  bool valid = false;
  fore(i, 1, n+1){
    if(state[i] == 0){ //we have not processed the node
      valid = dfs(adj, state, topo, i);

      if(not valid){ cout << "IMPOSSIBLE" << endl; return 0; }
    }
  }

  forr(i, n-1, 1) cout << topo[i] << " ";
  cout << topo[0] << endl;

}

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