LeetCode课程表问题：BFS检测环代码仅过42/52用例求排查

你总共需要修读numCourses门课程，课程编号从0到numCourses-1。给定先修课程数组prerequisites，其中prerequisites[i] = [ai, bi]表示修读ai前必须完成bi。返回是否能完成所有课程（存在环则无法完成）。

• 示例1：
  输入：numCourses = 2, prerequisites = [[1,0]]
  输出：true
  解释：修读课程1前需完成课程0，可完成所有课程。

• 示例2：
  输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
  输出：false
  解释：课程间形成环，无法完成。

我尝试用BFS检测环来解决该问题，但代码仅通过52个测试用例中的42个，请问代码存在什么错误？

class Solution {
public:
    bool finish(int course, unordered_map<int, list<int>>& adj,
                vector<int> visited) {

        visited[course] = 1;
        queue<pair<int, int>> q;
        q.push({course, -1});

        while (!q.empty()) {
            int node = q.front().first;
            int parent = q.front().second;
            q.pop();
            for (auto it : adj[node]) {
                if (!visited[it]) {
                    visited[it] = 1;
                    q.push({it, node});
                } 
                else if (parent != it) {
                    return false;
                }
            }
        }
        return true;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, list<int>> adj;
        for (int i = 0; i < prerequisites.size(); i++) {
            int u = prerequisites[i][0];
            int v = prerequisites[i][1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        vector<int> visited(numCourses, 0);

        for (int i = 0; i < numCourses; i++) {
            if (!visited[i]) {
                if (!finish(i, adj, visited)) {
                    return false;
                }
            }
        }
        return true;
    }
};

你的代码存在三个核心问题：

1. 邻接表构建错误
   课程先修关系是有向边，prerequisites[i] = [ai, bi]表示bi → ai的依赖（修ai必须先修bi），但你把它当成无向图处理，同时添加了u→v和v→u两条边。这会导致误判很多合法的有向无环图为有环，比如示例1的情况，你的邻接表会把0和1互相连接，BFS时会认为1的邻居0已经被访问且不是父节点，直接返回false，但实际这是合法的有向无环图。

2. visited参数传递错误
   你在finish函数中把visited按值传递（vector<int> visited），这意味着每次调用finish时都会创建一个新的副本，外层循环中visited数组的状态不会被更新。比如当处理多个连通分量时，之前访问过的节点在下次调用finish时会被重新标记为未访问，导致重复处理，甚至误判环的存在。应该改成引用传递：vector<int>& visited。

3. 环检测逻辑不适用于有向图
   你当前的BFS逻辑是用于无向图的环检测（通过父节点判断是否回环），但有向图的环检测需要不同的逻辑——需要跟踪当前遍历路径中的节点，而不仅仅是已访问的节点。正确的有向图BFS环检测应该用拓扑排序（入度表+队列），或者用DFS标记三种状态（未访问、正在访问、已访问）。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(numCourses);
        vector<int> inDegree(numCourses, 0);
        
        // 构建有向邻接表和入度表
        for (auto& p : prerequisites) {
            int ai = p[0];
            int bi = p[1];
            adj[bi].push_back(ai);
            inDegree[ai]++;
        }
        
        queue<int> q;
        // 加入所有入度为0的节点
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }
        
        int completed = 0;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            completed++;
            
            for (int neighbor : adj[node]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
        
        // 如果完成的课程数等于总课程数，说明无环
        return completed == numCourses;
    }
};

内容的提问来源于stack exchange，提问作者CS1133 vanshita rathore