gpt4 book ai didi

c++ - 在无向树中寻找最长路径

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:22:56 25 4
gpt4 key购买 nike

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

算法:

  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。

最佳答案

在我看来,一个问题是您应该在从被调用的递归函数返回时立即递减计数。

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

关于c++ - 在无向树中寻找最长路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30636886/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com