在C ++中使用双DFS查找树的直径

我正在SPOJ上尝试出现问题,该问题应该在树中任何两个节点之间找到最长的路径。输入由测试用例的数量t,节点的数量n,后跟由“ abl”给出的n-1条边组成,其中引用节点1,b引用节点2,l引用边缘的长度。我尝试使用double dfs方法,首先在节点1上执行dfs,以查找从节点1开始的最长路径。然后,在距离节点1最远的节点上执行dfs,以找到最长的距离。不幸的是,我的代码是错误的,我也不知道为什么会这样,我希望有人可以帮助我。提前致谢!

编辑:忘记提及我确实设法使用双BFS解决了问题。我想尝试使用DFS来解决它,因为据说DFS比BFS更易于实现,但是使用DFS却给了我错误的答案。

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> adj[50001];
bool visited[50001] = {0};
int maxdist = -1, maxnode = -1;

void dfs(int node, int d)
{
    visited[node] = 1;
    if (d > maxdist)
    {
        maxdist = d;
        maxnode = node;
    }
    for(auto u: adj[node])
    {
        if(!visited[u.first])
        {
            dfs(u.first, d+u.second);
        }

    }
    return;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        for (int i = 0; i < n-1; i++)
        {
            int a, b, l;
            cin >> a >> b >> l;
            adj[a].push_back(make_pair(b, l));
            adj[b].push_back(make_pair(a, l));
        }

        dfs(1, 0);
        for(int i = 1; i <= n; i++)
        {
            visited[i] = 0;
        }
        dfs(maxnode, 0);

        cout << maxdist << endl;

    }

}
评论