Butcher13's blog

By Butcher13, history, 3 weeks ago, In English

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;
    }
}
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

child vector is used for tracing the path