LeetCode Graph Valid Tree问题43/44测试用例不通过排查

问题分析 #

你提交的代码存在三个核心逻辑错误，刚好会导致你给出的测试用例判断错误：

错误1：环检测使用了单向邻接表 #

你在调用checkCycle时，给createAdjList传的第二个参数是false，这就导致环检测的邻接表只有单向边，比如边[1,7]只会记录1→7的关联，不会记录7→1的关联。你给出的测试用例中，环所在的子图包含节点1，而从0出发走单向边根本遍历不到节点1，自然无法检测到环的存在。

错误2：环检测逻辑适配错误 #

你当前的环检测逻辑是针对有向图设计的，用visiting和visited两个集合判断回溯时的环，但本题是无向图，无向图不需要visiting集合，反而需要记录每个节点的父节点：遍历到邻居节点时，如果邻居已经被访问过且不是当前节点的父节点，才判定为存在环。如果直接套用有向图的逻辑，就算你改成双向邻接表，也会把遍历到父节点的情况误判为环。

错误3：环检测未覆盖全图 #

你现在的环检测只从节点0开始遍历，如果图存在多个连通分量，其他连通分量里的环完全无法被检测到，会出现漏判。 #

修正方案 #

快速优化（可选） #

首先可以加一个前置判断：如果边的数量不等于n-1，直接返回false，因为树的充要条件就是n个节点恰好n-1条边且连通，这个判断可以直接筛掉大部分有环或者不连通的用例，甚至可以直接省去单独的环检测逻辑：只要满足边数=n-1且全连通，就一定是树，不会有环。

核心逻辑修正 #

如果要保留单独环检测的逻辑，按如下调整即可：

1. 环检测时调用createAdjList要传true，使用无向邻接表
2. 重写环检测逻辑适配无向图，同时遍历所有节点覆盖所有连通分量

修正后的环检测示例代码（BFS版本）

private boolean checkCycle(int n, int[][] edges) {
    HashMap<Integer, ArrayList<Integer>> adjList = this.createAdjList(n, edges, true);
    HashSet<Integer> visited = new HashSet<>();
    // 遍历所有节点，覆盖所有连通分量
    for (int i = 0; i < n; i++) {
        if (!visited.contains(i)) {
            Queue<int[]> queue = new LinkedList<>();
            // 队列存[当前节点, 父节点]，父节点初始设为-1
            queue.add(new int[]{i, -1});
            visited.add(i);
            while (!queue.isEmpty()) {
                int[] curr = queue.poll();
                int node = curr[0];
                int parent = curr[1];
                for (int neighbor : adjList.get(node)) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.add(new int[]{neighbor, node});
                    } else if (neighbor != parent) {
                        // 遇到已访问过且不是父节点的节点，存在环
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

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