### Butcher13's blog

By Butcher13, history, 3 weeks ago,

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;
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;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>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

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;
}
}

• -1

 » 3 weeks ago, # | ← Rev. 2 →   0 child vector is used for tracing the path