Topological sort

topsort.cpp

// https://cses.fi/problemset/task/1679/
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void dfs(vector<vector<ll>> &graph, vector<bool> &visited, vector<ll> &topsort, ll u) {
    if (visited[u]) return;
    visited[u] = true;
    for (ll i : graph[u]) {
        dfs(graph, visited, topsort, i);
    }
    // Since we push back when the function is called back from stack, the order of topsort will be reversed
    topsort.push_back(u);
}

vector<ll> topSort(vector<vector<ll>> &graph, ll n) {
    // Just merge all valid DFS path and the graph will be top sorted. Note that topsort only have n element
    // Because of this, top sort of a graph is not unique
    vector<bool> visited(n + 1);
    vector<ll> res;
    for (ll i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(graph, visited, res, i);
        }
    }
    reverse(res.begin(), res.end()); // Check comment at line 12
    return res;
}

bool isValid(vector<vector<ll>> &graph, ll n, vector<ll> &a){
    // A topological order is valid when the graph is Directed Acyclic Graph (a directed graph with no cycle)
    // Or simply, a topological order is valid when all child vertices appear later than its parents in top sort
    vector<ll> index(n + 1);
    for(ll i = 0; i < a.size(); i++) index[a[i]] = i;
    for(ll i = 1; i <= n; i++){
        for(ll j : graph[i]){
            if(index[i] > index[j]) return false;
        }
    }
    return true;
}

int main() {
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> graph(n + 1);
    while (m--) {
        ll a, b;
        cin >> a >> b;
        graph[a].push_back(b);
    }
    vector<ll> ans = topSort(graph, n);
    if(!isValid(graph, n, ans)) cout << "IMPOSSIBLE";
    else{
        for(ll i : ans) cout << i << ' ';
    }
}