Блог пользователя iamdumb

Longest path in the tree
Автор iamdumb, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 
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.

→ Ответить