Longest path in a DAG

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Longest path in a DAG

Post by tryit1 » Wed Sep 23, 2009 7:38 am

Longest path in a DAG. I've some problems for longest path in DAG with this function. Can you point out if it is correct.

Found it , visit is the culprit.

Code: Select all

int dfs(int x){
   visit[x]=true;
   if(dp[x]) return dp[x];
   int i,ans=1;
   for(i=0;i<g[x].size();i++){
      if(!visit[g[x][i]])      ans=max(ans,1+dfs(g[x][i]));
   }
   return dp[x]=ans;
}

In main:
memset(dp,0,sizeof(dp));
memset(visit,0,sizeof(visit));
for(i=0;i<n;i++){
      if(!visit[i]){
         ans=max(ans,dfs(i));
      }
   }

Post Reply

Return to “Algorithms”