CSES Longest Flight Route Soln

Revision en4, by Butcher13, 2024-06-24 19:32:06

I dont know if anyone came up with this soln but when I thought of this soln I got extremely happy and joyful. Here goes the logic: Basically we can use dfs to iterate through every node and use a dp table which holds the maximum distance of that node from the end node(n). Now the base case will be when we reach 'n' we return 1. Now for every other node we call dfs for all its adjacent nodes and return the value of that node as maximum of all the distances the adjacent node returns. At the same time we hold a child vector which stores the next node for each node. We do this in order to be able to trace the path. However, if we dont reach n we return 0. So that's the "IMPOSSIBLE" condition. So, dp[i] shows the max distance of that node from 'n'

int dfs(vector<int> adj[],int n,int node,vector<int>& dp,vector<int>& child){
if(node==n) return dp[n]=1;       //base case

if(dp[node]!=-1) return dp[node];   //If the value already exists

int maxi=0;
for(auto it:adj[node]){
int trav = dfs(adj,n,it,dp,child);       //calling dfs for adj nodes
int tmp = trav==0 ? 0 : 1+trav;
if(tmp>maxi){                  //updating the max value
child[node]=it;             //updating the child
maxi=tmp;
}
}
return dp[node] = maxi;
}

int main(){
int n,m;
cin>>n>>m;
vector<int> adj[n+1];
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
adj[a].push_back(b);
}
vector<int> dp(n+1,-1);     //dp that holds max distance of every node from n
vector<int> child(n+1,-1);  //holds the next node in the max distance path

int val = dfs(adj,n,1,dp,child);
if(val==0){
cout<<"IMPOSSIBLE";       //'n' node is unreachable
}
else{
cout<<val<<endl;
int node=1;
while(node!=n){         //printing the path
cout<<node<<" ";
node=child[node];
}
cout<<n;
}
}


#### History

Revisions

Rev. Lang. By When Δ Comment
en4 Butcher13 2024-06-24 19:32:06 39
en3 Butcher13 2024-06-24 18:05:35 1110 Added code
en2 Butcher13 2024-06-24 18:04:40 0 Added photos of code
en1 Butcher13 2024-06-24 18:03:40 788 Initial revision (published)