Longest path in DAG

longest_path_DAG.cpp

// https://cses.fi/problemset/task/1680
#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);
    }
    topsort.push_back(u);
}

vector<ll> topSort(vector<vector<ll>> &graph, ll n) {
    vector<bool> visited(n + 1);
    vector<ll> res;
    dfs(graph, visited, res, 1);
    reverse(res.begin(), res.end());
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> graph(n + 1), rGraph(n + 1);
    while(m--){
        ll a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        rGraph[b].push_back(a);
    }
    vector<ll> ts = topSort(graph, n);
    vector<ll> dist(n + 1), parent(n + 1);
    dist[1] = 1;
    for(ll i : ts){
        if(i == 1) continue;
        for(ll j : rGraph[i]){
            if(dist[i] < dist[j] + 1) {
                dist[i] = dist[j] + 1;
                parent[i] = j;
            }
        }
    }
    vector<ll> ans;
    for(ll i = n; i; i = parent[i]){
        ans.push_back(i);
    }
    reverse(ans.begin(), ans.end());
    if(!dist[n]){
        cout << "IMPOSSIBLE";
        return 0;
    }
    cout << ans.size() << '\n';
    for(ll i : ans) cout << i << ' ';
}