树节点之间最大距离的运行时错误

Question

这是一个 interviewbit.com 问题：https://www.interviewbit.com/problems/largest-distance-between-nodes-of-a-tree/

给定一个由 N (2 <= N <= 40000) 个节点组成的任意无权有根树。该问题的目标是找到树中两个节点之间的最大距离。两个节点之间的距离是节点之间路径上的边数（任何一对节点之间都会有一条唯一路径，因为它是一棵树）。节点将编号为 0 到 N - 1。

我正在使用 dfs 查找距离根节点最远的节点。从这个节点我正在做 DFS 来找到最远的节点。这个距离是必需的答案。我实现了它，但是在调用 do_dfs 函数时出现分段错误。我在每一行之后都写了 return 语句来找出我出错的地方。我已经在代码的注释中指出了这一行。

pair<int,int> do_dfs(vector<vector<int>> &adj, int n, int root)
{
    int l1 = 0;
    stack<pair<int,int>> st;
    st.push(make_pair(root,0));
    vector<int> vis(n,-1); 
    vis[root]=1;  //This statement is causing segmentation fault
    int longest=-1;

    while(!st.empty())
    {
        int top=st.top().first , l=st.top().second;
        int x=-1;
        for(int i=0;i<adj[top].size();++i)
        {
            int node = adj[top][i];
            if(vis[node] ==-1)
            {
                x = node;
                st.push(make_pair(node,l+1));
                vis[node]=1;
                break;
            }
        }

        if(x==-1)
        {
            if(l>l1)
            {
                l1 = l;
                longest = top;

            }
            st.pop();
        }
    }
    return make_pair(longest,l1);
}


int Solution::solve(vector<int> &A) 
{
    if(A.size()<3)return (A.size()-1);

    vector<vector<int>> adj(A.size());
    int root;
    for(int i=1;i<A.size();++i)
    {
        if(A[i]==-1)
        {
            root = i;
            continue;
        }
        adj[i].push_back(A[i]);
        adj[A[i]].push_back(i);
    }
    //adjacent list for graph complete

    pair<int,int> d1=do_dfs(adj,A.size(),root) ;
    pair<int,int> d2 = do_dfs(adj, A.size(), d1.first);
    int ans = d2.second;
    return ans;
}

特斯凯斯 :- A : [ -1, 0, 0, 1, 2, 1, 5 ] 预期输出：5

A : [ -1, 0, 0, 0, 3 ] 预期输出：3

Answer 1

更改Solution::solve(vector<int> &A)中的行：

for(int i = 1 ; i < A.size() ; ++i)

收件人：

for(int i = 0; i < A.size() ; ++i)

你的问题就解决了。

问题是您没有完全迭代给定的 A 数组。您从索引 1 开始迭代，而数组从索引 0 到 A.size() - 1。因此，您的邻接列表未正确构建，并且 root 变量在某些情况下仍未初始化。所以你运行变成了Runtime error。

树节点之间最大距离的运行时错误

Runtime error in Largest Distance between nodes of a Tree

c++

graph-theory

depth-first-search

graph-algorithm

data-structures