LeetCode 802题找到最终安全状态：BFS拓扑排序遇内存超限

先梳理你代码中的核心问题，这些问题直接导致了内存超限和逻辑异常：

关键错误点 #

• 错误的邻接表长度处理：用graph[0].length作为统一的m，但每个节点的邻接表长度各不相同，这会创建不必要的大数组（比如无用的V），直接触发内存超限，同时导致遍历逻辑错误。
• 循环变量错误：多个for循环中误将j++写成i++，比如初始化adjRev、遍历邻接表的循环，这会引发无限循环或错误的遍历次数，进一步加剧内存消耗。
• 无用内存占用：二维数组V完全未被使用，却占用大量内存，是内存超限的直接诱因之一。
• 未初始化的邻接表：adj集合未初始化就直接调用adj.get(i)，会抛出空指针异常，且反转图的构建逻辑完全错误。
• 拓扑排序逻辑颠倒：原问题中安全节点是出度为0的终端节点，反转图后应将原节点的出度作为反转图的入度，你的代码逻辑完全搞反。

修正后的代码 #

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        // 初始化反转图的邻接表
        List<List<Integer>> adjRev = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjRev.add(new ArrayList<>());
        }
        // 统计原节点的出度（对应反转图的入度）
        int[] outDegree = new int[n];
        
        // 构建反转图并统计出度
        for (int i = 0; i < n; i++) {
            for (int neighbor : graph[i]) {
                // 原边为i -> neighbor，反转后为neighbor -> i
                adjRev.get(neighbor).add(i);
                outDegree[i]++;
            }
        }
        
        Queue<Integer> q = new LinkedList<>();
        // 初始加入出度为0的终端安全节点
        for (int i = 0; i < n; i++) {
            if (outDegree[i] == 0) {
                q.add(i);
            }
        }
        
        List<Integer> safeNodes = new ArrayList<>();
        while (!q.isEmpty()) {
            int node = q.poll();
            safeNodes.add(node);
            // 遍历反转图中当前节点的邻接节点，减少其出度
            for (int prevNode : adjRev.get(node)) {
                outDegree[prevNode]--;
                if (outDegree[prevNode] == 0) {
                    q.add(prevNode);
                }
            }
        }
        
        Collections.sort(safeNodes);
        return safeNodes;
    }
}

修改说明 #

1. 移除无用内存：删除完全未使用的二维数组V，直接减少内存占用。
2. 正确处理邻接表：不再用统一的m，而是遍历每个节点自身的邻接表长度，避免内存浪费和数组越界。
3. 修复循环变量：修正所有写错的循环变量，或改用增强for循环避免变量错误。
4. 正确构建反转图：按照原边i→neighbor反转成neighbor→i的逻辑构建反转图，同时统计原节点的出度。
5. 修正拓扑排序逻辑：从出度为0的终端节点开始，逐步减少反转图中邻接节点的出度，当出度为0时，说明该节点所有路径均指向安全节点，将其加入安全列表。

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