在无向树中查找最长路径

Question

我试图在无向树中找到最长的路径（http://www.spoj.com/problems/PT07Z/）并提出以下代码。

#include <iostream> 
#include <vector> 

using namespace std; 

vector< vector<int> > graph; 
int q=0, m = -1;        // m is for largest path and q is one of the end vertex of that path 

void dfs(int i, int count, vector<bool>& v) 
{ 
    v[i] = true; 
    for(int j=0;j<graph[i].size();j++) 
    { 
     if(!v[graph[i][j]]) 
     { 
      count++;       // count is the length of the path from the starting vertex to current vertex 
      dfs(graph[i][j], count, v); 
     } 
    } 
    if(count>m) 
    { 
     m= count; 
     q=i; 
    } 
    count--;         // decreasing count since the method return to its calling function 
} 


int main() 
{ 
    int n, x, i, y; 
    cin>>n; 
    graph = vector< vector<int> >(n); 
    vector<bool> visited(n); 
    vector<bool> v(n); 
    for(i=0;i<n-1;i++) 
    { 
     cin>>x>>y; 
     x--, y--; 
     graph[x].push_back(y); 
     graph[y].push_back(x); 
    } 
    dfs(0, 0, visited); 
    m=-1; 
    cout<<q<<endl; 
    dfs(q, 0, v); 
    cout<<q<<endl; 
    cout<<m<<endl; 
} 

谁能告诉我这里有什么问题，因为我得到的路径（M）的最大长度的错误值虽然最长路径结束顶点是正确的（ATLEAST上，我曾尝试测试用例）。我试图实现以下算法在这里：

算法：

1. 运行DFS从任何节点找到最远的叶节点。标记该节点T.
2. 运行另一个DFS以从T中找到最远的节点。
3. 在步骤2中找到的路径是树中最长的路径。

一些测试用例： 第一：

17 
1 2 
1 3 
2 4 
2 5 
3 6 
3 7 
6 8 
6 9 
8 10 
9 11 
7 12 
7 13 
13 14 
13 15 
15 16 
15 17 

这个测试案例正确答案是7

二：

7 
1 2 
1 3 
2 4 
2 5 
3 6 
3 7 

正确答案为这个测试案例是4

Answer 1

只需从'for'循环中移除该计数++并移除该计数 - ;

并在开始时保持'count ++'。

void dfs(int i, int count, vector<bool>& v) 
{ 
    count++; 
    v[i] = true; 
    for(int j=0;j<graph[i].size();j++) 
    { 
     if(!v[graph[i][j]]) 
     { 
      dfs(graph[i][j], count, v); 
     } 
    } 
    if(count>m) 
    { 
     m= count; 
     q=i; 
    } 
} 

Answer 2

一个问题acc对我来说就是你应该在被调用的递归函数返回时立即递减计数。

for(int j=0;j<graph[i].size();j++) 
    { 
     if(!v[graph[i][j]]) 
     { 
      count++;       
      dfs(graph[i][j], count, v); 
      count--; 
     } 

或者干脆：

for(int j=0;j<graph[i].size();j++) 
    { 
     if(!v[graph[i][j]])   
      dfs(graph[i][j], count+1, v); 

这是因为计数不应该不断递增为graph[i]每个邻居。