Longest path in a tree

I was solving this problem onn spoj Problem. What I am doing is choosing a leaf node as the start point of dfs and counting the max edges at each point that I can get… Is that approach wrong . Here is my code it fails on test case 5 on spoj.

#include<bits/stdc++.h>
 using namespace std;
 list <int> adj[10001];
 bool visited[10001];
 int dfs(int start)
 {
list <int>::iterator ii;
int high=0;
for(ii=adj[start].begin();ii!=adj[start].end();ii++)
    if(!visited[*ii])
    {
        visited[*ii]=true;
        high=max(high,dfs(*ii)+1);
    }
return high;
}
int main()
{
int V,i,j,k,buff,l,r;
scanf("%d",&V);
if(V==1)
{
    scanf("%d%d",&l,&r);
    printf("0\n");
    exit(0);
}
for(i=1;i<=V-1;i++)
{
    scanf("%d%d",&l,&r);
    adj[l].push_back(r);
    adj[r].push_back(l);
}

for(i=1;i<=V;i++)
    {
    if(adj[i].size()==1)
        break;
    }
visited[i]=true;
printf("%d\n",dfs(1));
return 0;

}

1 Like

Leave it,I got it The longest distance will be from one of the leaf not from any leaf…!

This approach is wrong. Imagine that you have long bamboo and also one leaf somewhere near the middle of it. Longest path is between the ends of bamboo, but if you’ll choose that leaf as starting point - your path will be almost twice shorter.

However, solution is quite easy. Pick any leaf, run dfs from it to find furthest vertex; now start dfs once again from this new vertex. This second dfs will give you longest path.

2 Likes

Bfs and Bfs needed :smiley:

I have no that much knowledge about the programming. But after analyzing the program you have given i got confused. I am sure there is something mistake you have done on your code. Better to make sure that with your seniors. They will provide the correct code for finding longest path in a tree.

Ayurveda treatment therapies Kerala

This problem can be solved with a singular dfs very easily. Choose any node which has only 1 outgoing/incoming edge using a for loop. Then just run dfs from that node and save the vertex which has the furthest distance from the original vertex.
This works since it is a tree, meaning for any two nodes there is exactly one route between them.

I think I can solve it using single DFS too… Let me try :slight_smile:

can you give small proof for this argument . I didnt get it. How dfs from new verex give longest path. ?