rishi2674's blog

By rishi2674, history, 5 months ago, In English

This is a very simple and detailed solution for the CSES problem Longest Flight Route which a problem involving graph theory. The problem statement aims to find the longest route between 2 cities (1 and n) such that the route covers maximum no of distinct cities in the route. If we cannot reach the nth node from the 1st node, "IMPOSSIBLE" has to be printed. Else, print the length of route along with the cities encountered.

The solution of this problem can be intuitively thought to be to find the maximum route using the depth first traversal in a graph. 1. The input is taken as an adjacency list represented the edges in a directed graph. 2. A visited array and mark_dfs() function is used to check whether nth node is reachable or not. If it is not reachable, "IMPOSSIBLE" is printed. 3. The core logic of the solution lies in storing the maximum distance of a node from the nth node in the dp array. A dfs is implemented from the 1st node traversing to all the child nodes. The nth node returns a len of 1 which is the base case of recursion. Whenever a len greater than the already stored len is encountered, the max_len is updated and stored in the dp array as supposed to a basic dynamic programming approach. 4. The child array stores the child_node which gave the max_len route which is used to print the path of flight and used in forward traversal. 5. The printing of route involves forward traversal in the child array, where the node is reallocated to the child[node] in each pass until we reach the nth node. 6. The time complexity of the above approach is O(n+m) for the mark_dfs() function. The time complexity of dfs() is O(n) as the dp approach reduces the dfs to a linear time complexity. Hence the overall time complexity can be around O(2n+m) or O(n) for simplified purposes. 7. The space complexity of given approach is O(3n) wherein three arrays namely, vis,child and dp are used for functional purposes.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD1 998244353
#define INF 1e18
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define set_bits __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define fori(i,a,b) for(int i=a; i<b;i++)
#define Y { cout <<"YES"<< endl;}
#define NN { cout <<"NO"<< endl;}

const int mod = 1e9+7;


//function to check whether nth node is reachable
void mark_dfs(ll node, vector<ll> &vis, vector<ll> adj[]){
    vis[node] = 1;
    for(auto child : adj[node]){
        if(!vis[child]){
            mark_dfs(child,vis,adj);
        }
    }
}

//function to return the max_len and store the path using child array
ll dfs(ll node, vector<ll> &dp, vector<ll> adj[],int n, vector<ll> &child){
    //base condition
    if(node==n) return dp[n] = 1;
    //memoization step
    if(dp[node]!=-1) return dp[node];
    ll len = 0;
    //standard dfs approach
    for(auto v : adj[node]){
        ll tmp = dfs(v,dp,adj,n,child);
        //temp_len checks whether the len is coming from the nth node or not
        ll temp_len = tmp==0?0:1+tmp;
        if(temp_len>len){
            // updating the child node and len
            child[node] = v;
            len = temp_len;
        }
    }
    //dp assignment step
    return dp[node] = len;
}
 
int main(){
    ll n,m;
    cin>>n>>m; 
    vector<ll> adj[n+1];
    fori(i,0,m){
        ll x,y;
        cin>>x>>y;
        adj[x].pb(y);
    }

    vector<ll> vis(n+1,0);
    //function call to check if nth node is reachable
    mark_dfs(1,vis,adj);
    if(!vis[n]) cout<<"IMPOSSIBLE\n";
    else{
        vector<ll> dp(n+1,-1);
        vector<ll> child(n+1,0);
        ll len = dfs(1,dp,adj,n,child);
        int node = 1;
        vector<ll> path;
        //forward traversal to print the path.
        while(node){
            path.pb(node);
            node = child[node];
        }
        cout<<len<<endl;
        for(auto it : path){
            cout<<it<<" ";
        }
    }
    return 0;

}

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why storing the parent of the nodes in the longest path instead of childs in not working?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it is because the distances are being evaluated respect to the nth node, and not from the start node like in dijkstra. When comparing tmp_len with the current len, you are considering just the childs of the current node, and not other paths that go from outside. So it is like we were trying to find the path from the nth node to the 1st node, and reconstructing the path from there.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can we not do it using dijkstra's algorithm, but just assuming -1 cost for all the edge pairs ?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dijkstra's algorithm doesnt work for negative weight.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dijkstra's algorithm here gives TLE due to higher time complexity, otherwise does work.

    [You can make Dijkstra work by using +1 cost for edge pairs and max_heap.]

    [In this case Dijkstra will work for -1 cost too.]

    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, Dijkstra will not work for negative edge weights.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can do without dp as well, using a modification to Kahn's algorithm(very similar to bfs):

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin(), v.end()
#define veci vector<int>
#define pb push_back
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int minf = -1e18;


veci dist;
vector<veci> g;
veci par;
veci indeg; // stores indegrees of the nodes
void solve(){
    int n,m;
    cin>>n>>m;
    g.resize(n+1);
    dist.assign(n+1,minf); // set all distances to minus infinity
    par.assign(n+1,0);
    indeg.assign(n+1,0);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        g[a].pb(b);
        indeg[b]++;
    }
    dist[1]=0;
    queue<int> q;
    for(int i=1;i<=n;i++)if(indeg[i]==0)q.push(i);
    while(!q.empty()){
        int curr = q.front();
        q.pop();
        for(auto child:g[curr]){
            indeg[child]--;
            if(dist[child]<dist[curr]+1){
                dist[child]=dist[curr]+1;
                par[child]=curr;
            }
            if(indeg[child]==0)q.push(child);
        }
    }
    if(dist[n]<0)cout<<"IMPOSSIBLE"; // since number of nodes <=1e5 thus minf + anything will never give a positive distance
    else{
        veci ans;
        int x = n;
        while(x!=0){
            ans.pb(x);
            x=par[x];
        }
        reverse(all(ans));
        cout<<ans.size()<<"\n";
        for(auto &el:ans)cout<<el<<" ";
    }
}

int32_t main(){
    FIO;
    clock_t tStart = clock();
    int t = 1;
    // cin >> t;
    for(int i=1;i<=t;i++){
        // cout<<"Case #"<<i<<": ";
        solve();
    }
    // cerr<<fixed<<setprecision(6)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
}