LeetCode 2360：最长环问题DFS实现无环图时出现段错误求助

问题描述 #

在LeetCode第2360题（每个节点最多有一条出边的图中寻找最长环）中，我用DFS实现的代码在有环图中结果正确，但无环图会出现段错误，求帮忙排查问题。

实现代码 #

#include <bits/stdc++.h>
using namespace std;

void dfs(vector<int> &edges, vector<int> &vis, vector<int> &dist, int node, int &ans)
{
    vis[node] = 1;

    int nb = edges[node];
    if (!vis[nb] && nb!=-1)
    {
        dist[nb] = dist[node] + 1;
        dfs(edges, vis, dist, nb, ans);
    }
    else if( nb!=-1)
    {
        ans = max(ans, dist[node] -dist[nb]  + 1);
    }
}
int longestCycle(vector<int> &edges)
{
    int n = edges.size();
    vector<int> vis(n, 0), dist(n, 0);
    int ans = -1;
    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            // dist[i] = 1;
            dfs(edges, vis, dist, i, ans);
        }
    }
    return ans;
}

int main() {
    vector<int> edges={2,-1,3,1};
    // vector<int> edges={3,3,4,2,3};
    cout<<longestCycle(edges);
}

错误原因 #

段错误的核心是数组越界访问：

• 代码中if (!vis[nb] && nb!=-1)的判断顺序错误，先访问了vis[nb]再判断nb是否为-1。当edges[node]是-1时，nb=-1，访问vis[-1]会直接触发数组越界，导致段错误。

修复后的代码 #

#include <bits/stdc++.h>
using namespace std;

void dfs(vector<int> &edges, vector<int> &vis, vector<int> &dist, int node, int &ans)
{
    vis[node] = 1;

    int nb = edges[node];
    // 先判断nb有效性，再检查是否访问过
    if (nb != -1 && !vis[nb])
    {
        dist[nb] = dist[node] + 1;
        dfs(edges, vis, dist, nb, ans);
    }
    else if (nb != -1)
    {
        // 仅当nb属于当前DFS路径时，才计算环长
        if (dist[nb] != 0)
        {
            ans = max(ans, dist[node] - dist[nb] + 1);
        }
    }
    // 回溯时重置dist，避免干扰其他路径遍历
    dist[node] = 0;
}
int longestCycle(vector<int> &edges)
{
    int n = edges.size();
    vector<int> vis(n, 0), dist(n, 0);
    int ans = -1;
    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            dist[i] = 1; // 初始化起点路径长度
            dfs(edges, vis, dist, i, ans);
        }
    }
    return ans;
}

int main() {
    vector<int> edges={2,-1,3,1};
    // vector<int> edges={3,3,4,2,3};
    cout<<longestCycle(edges);
}

额外优化说明 #

1. 调整判断顺序：先检查nb != -1，再访问vis[nb]，彻底避免越界。
2. 初始化起点路径长度：原代码注释掉dist[i] = 1会导致路径长度计算错误，必须给DFS起点的dist赋值1。
3. 回溯重置dist：DFS结束后把当前节点的dist设为0，防止后续遍历其他路径时，错误引用旧路径的dist值。
4. 环有效性校验：新增dist[nb] != 0判断，确保计算的环是当前DFS路径中的环，避免误算其他已访问路径的节点。

内容的提问来源于stack exchange，提问作者Vegeta_sama