iamdumb's blog

Longest path in the tree
By iamdumb, history, 9 years ago, In English

Hello everyone,I was trying to do this question from spoj.First I had no idea how to do this question so,I googled and algorithms that came out was this

Algorithm: Run BFS from any node to find the farthest leaf node. Label that node T. Run another BFS to find the farthest node from T. The path you found in step 2 is the longest path in the tree.

But my problem is that it is becoming really very difficult to implement what is asked.Can anybody show me the code what is asked.Preferably in C++ and using dfs.Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your algorithm seems to be correct.

Here's my AC C++ code.

I have used BFS which is a slight overkill for this problem, but this can also be done using simple DFS.

The code is for reference purpose and

It is recommended that you code the solution by yourself and do not copy the entire solution as it is.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
void dfs(int v,int l){
visited[v]=true;
int i;
for(i=0;i<s[v].size();i++){
    if(!visited[s[v][i]]){
        dfs(s[v][i],l+1);
 
    }
}
if(l>best){
            best=l;
            node=v;
        }
visited[v]=false;
 
}
  1. v = current vertex of the tree
  2. l = distance of v from the source/root vertex
  3. s = adjacency list

Hope you understand the code.

→ Reply