在无向树中寻找最长路径

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) 的错误值，尽管最长路径的末端顶点是正确的（至少在我尝试过的测试用例中）。我试图在这里实现以下算法：

算法：

运行 DFS从任意节点寻找最远的叶节点。标记该节点 T.
运行另一个DFS，求T最远的节点。
您在第 2 步中找到的路径是树中最长的路径。

一些测试用例：第一：

此测试用例的正确答案是 7。

第二个：

此测试用例的正确答案是 4。

Answer 1

根据我的说法，一个问题是您应该从被调用的递归函数中立即递减 return 上的计数。

    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] 的每个邻居的计数不应保持递增。

Answer 2

只需从 'for' 循环中删除那个 count++ 并删除那个 count--;

并在函数开始时保持 '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;
    } 
}

在无向树中寻找最长路径

Finding longest path in an undirected tree

c++

algorithm

tree

depth-first-search