Longest Flight Route

Uolevi has won a contest, and the prize is a free flight trip that can consist of one or more flights through cities. Of course, Uolevi wants to choose a trip that has as many cities as possible.

Uolevi wants to fly from Syrjälä to Lehmälä so that he visits the maximum number of cities. You are given the list of possible flights, and you know that there are no directed cycles in the flight network.

Example:

Input:  n = 5, m = 5, edges = {{1, 2}, {2, 5}, {1, 3}, {3, 4}, {4, 5}}

Output:

4
1 3 4 5 

Approach:

C++

#include <bits/stdc++.h>
using namespace std;
vector<long long int> arr[1000001];
long long int vis[1000001];
vector<long long int> res;
long long int INF = -10000000000;
long long int n;
void dfs(long long int node)
{
    vis[node] = 1;
    for (long long int child : arr[node])
    {
        if (vis[child] == 0)
            dfs(child);
    }
    res.push_back(node);
}
void toposort()
{
    for (long long int i = 1; i <= n; i++)
        vis[i] = 0;
    res.clear();
    for (long long int i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
            dfs(i);
    }
    reverse(res.begin(), res.end());
}
int main()
{
    long long int m;
    n = 5, m = 5;
    vector<vector<long long int>> edges = {{1, 2},
                                           {2, 5},
                                           {1, 3},
                                           {3, 4},
                                           {4, 5}};
    for (int i = 0; i < m; i++)
    {
        long long int a = edges[i][0];
        long long int b = edges[i][1];

        arr[a].push_back(b);
    }
    toposort();

    long long int dist[n + 1];
    for (long long int i = 1; i <= n; i++)
        dist[i] = INF;
    dist[1] = 0;
    long long int parent[n + 1] = {-1};
    for (long long int i = 0; i < res.size(); i++)
    {
        long long int node = res[i];
        for (long long int child : arr[res[i]])
        {
            if (dist[res[i]] + 1 > dist[child])
            {
                dist[child] = dist[res[i]] + 1;
                parent[child] = res[i];
            }
        }
    }
    if (dist[n] < 0)
        cout << "IMPOSSIBLE\n";
    else
    {
        vector<long long int> path;
        for (long long int i = n; i != -1; i = parent[i])
            path.push_back(i);
        cout << dist[n] + 1 << "\n";
        reverse(path.begin(), path.end());
        for (long long int i = 1; i < path.size(); i++)
            cout << path[i] << " ";
    }
    return 0;
}