detect a cycle using BFS , there is a question on leetcode about course schedule

Question

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

if there is a cycle that means it would be impossible to complete all courses . only 42 test cases are passing out of 52 what am i doing wrong

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;
    }
};

this is my code

Answer 1

There are a few issues:

• The description is about a directed graph, yet you define each edge in both directions, making it an undirected graph. This is not correctly reflecting the problem

• If there are two paths that start in distinct nodes (each starting in canFinish), but which arrive at the same node, this doesn't mean there is a cycle, yet your code identifies such a situation as a cycle. It doesn't help that you use a bread-first traversal. You could use a depth-first traversal and then mark the nodes that are on the current path with a specific value in visited. Once you have visited all children of a node, you can mark that node with another value, to indicate it is no longer on the path. Only when you encounter a node that is already on the current path, you have a cycle.

• You haven't passed visited by reference, and so a copy is used in the finish function, which doesn't affect the caller's vector.

Here is a fix:

class Solution {
public:
    bool finish(int course, unordered_map<int, list<int>>& adj,
                vector<int> &visited) { // Pass by reference!
        visited[course] = 1; // Use a distinct value for a node one the current path
        for (auto it : adj[course]) { // Not breadth-first, but depth-first
            if (visited[it] == 1 || !visited[it] && !finish(it, adj, visited)) {
                return false;
            }
        }
        visited[course] = 2; // Completed
        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[v].push_back(u); // The graph is directed. No back reference!
        }
        vector<int> visited(numCourses, 0);
        
        for (int i = 0; i < numCourses; i++) {
            if (!visited[i] && !finish(i, adj, visited)) {
                return false;
            }
        }
        return true;
    }
};