c++breadth-first-searchcycle

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


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


Solution

  • There are a few issues:

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