207. Course Schedule

📝 Problem Details

• Title: 207. Course Schedule
• Link: https://leetcode.com/problems/course-schedule/
• Difficulty: Medium
• Tags/Categories: Graphs DFS Adjacency-List

input integer numCourses representing the total number of course you need to take labeled from 0 - numCourses-1 input array prerequisites where prerequisites[i] = [ai,bi] indicating you must take bi first if you want to take ai return true if you can take all courses and false otherwise

💭What Were My Initial Thoughts?

graph representation:
- each course is a ndoe
- a prerequisite means you must take A before B forming a directed edge

goal:
- if there is a cycle in the graph, its impossible to finish all courses
- if there is no cycle return true

- we are looking for cycles in a directed graph
- we can perform a dfs on our prerequisites and if we encounter the starting node on the path we know its a cycle and return false

💡 Explanation of Solution

1. build an adjacency list
- convert the prerequisites list into a directed adjacency list

2. DFS to detect cycles
- use DFS with cycle detection
	- maintain a visited array
		- 0 = unvisited
		- 1 = visiting (part of current DFS patg)
		- 2 = processed (no cycle found in this path)
- if we revisit a node marked 1, we have found a cycle
- if we reach a node marked 2, we can safely return true (already processed)

⌛ Complexity Analysis

Time Complexity: O(V+E) - DFS visits each node and edge once
Space Complexity: O(V+E) - Adjacency list + recursion stack

💻 Implementation of Solution

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 0 = unvisited
        // 1 = visiting
        // 2 = processed
        vector<int> visited(numCourses, 0); 
 
        // construct adjacency list
        vector<vector<int>> adjList(numCourses);
        for(const auto& prereq : prerequisites) {
            // prerequisites elements will always be a pair 
            int course = prereq[0];
            int pre = prereq[1];
            adjList[pre].push_back(course);
        }
 
        // run dfs for cycle detection
        for(int i=0; i < numCourses; i++) {
            if(visited[i] == 0) {
                if(hasCycle(i, adjList, visited)) 
                    return false;
            }
        }
        return true;
    }
 
private:
    bool hasCycle(int node, vector<vector<int>>& adjList, vector<int>& visited) {
        if(visited[node] == 1) return true; // cycle detected
        if(visited[node] == 2) return false; // already processed
 
        visited[node] = 1; // mark as visiting
 
        for(int neighbour : adjList[node]) {
            if(hasCycle(neighbour, adjList, visited))
                return true;
        }
 
        visited[node] = 2; // mark as processed
        return false;
    }
};