Course Schedule

#include <bits/stdc++.h>

#define REP(i, a, b) for (int i = a; i < b; i++)

// Type Aliases for 1D and 2D vectors with initialization
#define vll(n, val) vector<long long>(n, val) // 1D vector of long longs with size n, initialized to val
#define ll long long
#define vvi(n, m, val) vector<vector<int>>(n, vector<int>(m, val))              // 2D vector of ints (n x m), initialized to val
#define vvll(n, m, val) vector<vector<long long>>(n, vector<long long>(m, val)) // 2D vector of long longs (n x m), initialized to val

using namespace std;

void print_vector(vector<int> &x)
{
    for (int v : x)
    {
        cout << v << " ";
    }
    cout << "\n";
}

void print_matrix(vector<vector<int>> &matrix)
{
    cout << "\n"
         << "----------------" << "\n";
    for (vector<int> row : matrix)
    {
        print_vector(row);
    }
    cout << "\n"
         << "----------------" << "\n";
}

int calc_max_digit(int n)
{
    int max_digit = 0;
    while (n > 0 && max_digit < 9)
    {
        int digit = n % 10;
        if (digit > max_digit)
        {
            max_digit = digit;
        }
        n /= 10;
    }
    return max_digit;
}

// edges as edge list for outgoing node as pairs (end, cost)
vector<ll> dijkstras(int start_point, vector<vector<pair<int, int>>> edges)
{
    int n = edges.size();
    vector<bool> processed(n, false);
    vector<ll> distances(n, LLONG_MAX);
    distances[start_point] = 0;
    priority_queue<pair<ll, int>> pq;
    pq.push({0, start_point});
    while (!pq.empty())
    {
        int curr = pq.top().second;
        pq.pop();
        if (processed[curr])
        {
            continue;
        }
        processed[curr] = true;
        ll distance = distances[curr];

        for (pair<int, int> edge : edges[curr])
        {

            if (distance + edge.second < distances[edge.first])
            {
                distances[edge.first] = distance + edge.second;
                pq.push({-distances[edge.first], edge.first});
            }
        }
    }
    return distances;
}

bool topological_sort_dfs(int s, vector<vector<int>> &adj, vector<short> &status, vector<int> &result)
{
    if (status[s] == 1)
    {
        return false;
    }
    else if (status[s] == 2)
    {
        return true;
    }
    status[s] = 1;
    // process node s
    for (auto u : adj[s])
    {
        bool acylic = topological_sort_dfs(u, adj, status, result);
        if (!acylic)
        {
            return false;
        }
    }
    status[s] = 2;
    result.push_back(s);
    // cout << "Finished " << s << "\n";
    return true;
}

bool topological_sort(vector<vector<int>> &adj, vector<int> &result, int start = 0)
{
    int n = adj.size();
    vector<short> status(n, 0);

    for (int i = start; i < n; i++)
    {
        if (status[i] == 0)
        {
            bool acyclic = topological_sort_dfs(i, adj, status, result);
            if (!acyclic)
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n + 1, vector<int>());

    for (int i = 0; i < m; i++)
    {
        int start, end;
        cin >> start >> end;
        adj[start].push_back(end);
    }

    vector<int> result;

    bool acylic = topological_sort(adj, result, 1);

    if (!acylic)
    {
        cout << "IMPOSSIBLE";
    }
    else
    {
        for (vector<int>::reverse_iterator riter = result.rbegin();
             riter != result.rend(); ++riter)
        {
            cout << *riter << " ";
        }
        // for (int o : result)
        // {
        //     cout << o << " ";
        // }
    }

    cout << 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