Course Schedule

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <utility>
#include <vector>
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// Debug printing
#ifdef DEBUG
#define deb(fmt, args...) printf("DEBUG: %d: " fmt, __LINE__, ##args)
#else
#define deb(fmt, args...)
#endif

vector<int> top_sort;
bool impossible = false;

void dfs(int s, vector<int> &status, vector<int> adj[])
{
	if (impossible) return;
	if (status[s] == 1) {
		impossible = true;
	}
	if (status[s] == 2) {
		return;
	};
	status[s] = 1;
	for (auto u : adj[s]) {
		dfs(u, status, adj);
	}
	status[s] = 2;
	top_sort.push_back(s);
}

int main(int argc, char *argv[])
{
	// Read the input parameters
	int n, m;
	cin >> n >> m;

	// Read pairs from multiple lines
	vector<pair<int, int>> input_pairs(m);
	for (int i = 0; i < m; i++) {
		cin >> input_pairs[i].first >> input_pairs[i].second;
	}

	vector<int> adj[n + 1];

	// Add edges to adjacent structure
	for (int j = 0; j < m; j++) {
		adj[input_pairs[j].first].push_back(input_pairs[j].second);
	}

	vector<int> status(n + 1, 0);
	for (int i = 1; i < n + 1; i++) {
		if (status[i] == 0)
			dfs(i, status, adj);
	}

	if (impossible) {
		cout << "IMPOSSIBLE";
		return 0;
	}

	for (int i = n - 1; i >= 0; i--) {
		cout << top_sort[i] << " ";
	}
	cout << "\n";

	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