207. Course Schedule (Detecting Cycles in a Graph) - Leetcode Solution
Solution code💡 Step-by-Step Thought Process
- Understand the problem: Determine if it’s possible to finish all courses given prerequisites, by detecting if there’s a cycle in the graph.
- Create an adjacency list using a defaultdict to store the graph, where each course maps to its prerequisites.
- Initialize a states array with UNVISITED (0) for each course to track visit status.
- Define a DFS function that takes a node (course) and returns False if a cycle is detected, True otherwise.
- In DFS, if the node is VISITING (1), a cycle is detected, return False.
- If the node is VISITED (2), return True as it’s already processed.
- Mark the node as VISITING, then recursively check all its neighbors (prerequisites).
- If any neighbor returns False, return False.
- Mark the node as VISITED and return True.
- Run DFS for each course; if any returns False, return False.
- Return True if no cycles are detected.
Code Solution
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
g = defaultdict(list)
courses = prerequisites
for a, b in courses:
g[a].append(b)
UNVISITED = 0
VISITING = 1
VISITED = 2
states = [UNVISITED] * numCourses
def dfs(node):
state = states[node]
if state == VISITED: return True
elif state == VISITING: return False
states[node] = VISITING
for nei in g[node]:
if not dfs(nei):
return False
states[node] = VISITED
return True
for i in range(numCourses):
if not dfs(i):
return False
return True
# Time Complexity: O(N + E)
# Space Complexity: O(N + E)
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int, vector<int>> graph;
for (const auto& pair : prerequisites) {
graph[pair[0]].push_back(pair[1]);
}
vector<int> states(numCourses, 0); // 0: UNVISITED, 1: VISITING, 2: VISITED
for (int i = 0; i < numCourses; ++i) {
if (!dfs(i, graph, states)) {
return false;
}
}
return true;
}
private:
bool dfs(int node, unordered_map<int, vector<int>>& graph, vector<int>& states) {
if (states[node] == 1) return false; // Cycle detected
if (states[node] == 2) return true; // Already visited
states[node] = 1; // Mark as visiting
for (int neighbor : graph[node]) {
if (!dfs(neighbor, graph, states)) {
return false;
}
}
states[node] = 2; // Mark as visited
return true;
}
};
import java.util.*;
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] pair : prerequisites) {
graph.computeIfAbsent(pair[0], k -> new ArrayList<>()).add(pair[1]);
}
final int UNVISITED = 0;
final int VISITING = 1;
final int VISITED = 2;
int[] states = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
if (!dfs(i, graph, states)) {
return false;
}
}
return true;
}
private boolean dfs(int node, Map<Integer, List<Integer>> graph, int[] states) {
if (states[node] == 1) return false; // Cycle detected
if (states[node] == 2) return true; // Already visited
states[node] = 1; // Mark as visiting
if (graph.containsKey(node)) {
for (int neighbor : graph.get(node)) {
if (!dfs(neighbor, graph, states)) {
return false;
}
}
}
states[node] = 2; // Mark as visited
return true;
}
}
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
var canFinish = function(numCourses, prerequisites) {
const graph = new Map();
for (const [course, prereq] of prerequisites) {
if (!graph.has(course)) {
graph.set(course, []);
}
graph.get(course).push(prereq);
}
const UNVISITED = 0;
const VISITING = 1;
const VISITED = 2;
const states = new Array(numCourses).fill(UNVISITED);
const dfs = (node) => {
if (states[node] === VISITING) return false; // Cycle detected
if (states[node] === VISITED) return true; // Already visited
states[node] = VISITING; // Mark as visiting
if (graph.has(node)) {
for (const neighbor of graph.get(node)) {
if (!dfs(neighbor)) {
return false;
}
}
}
states[node] = VISITED; // Mark as visited
return true;
};
for (let i = 0; i < numCourses; i++) {
if (!dfs(i)) {
return false;
}
}
return true;
};
Detailed Explanation
Understanding the Problem
You're given a set of courses, labeled from 0 to numCourses - 1, and a list of prerequisite pairs. Each pair [a, b] means course a requires course b to be completed first. Your task is to determine if it's possible to finish all the courses. This boils down to detecting whether the prerequisite structure contains any cycles — if it does, completing all courses is impossible.
Modeling the Problem
We can model this as a directed graph:
- Each course is a node.
- Each prerequisite pair [a, b] becomes a directed edge from b to a.
- If this graph has a cycle, then there's a circular dependency, and we cannot complete all the courses.
Approach: DFS with Cycle Detection
The goal is to perform a depth-first traversal (DFS) on each node and detect cycles. To do this, we use a state tracking array for all nodes:
0= UNVISITED: the course has not been checked yet.1= VISITING: we're currently exploring this course’s prerequisites.2= VISITED: the course and all its descendants have been verified and no cycle was found.
Step-by-Step Execution
1. Build the graph: Use an adjacency list to represent which courses depend on which prerequisites.
2. Initialize visit state: Create a state array of size numCourses initialized to 0 (UNVISITED).
3. Define DFS: For each course, recursively traverse its prerequisites.
4. Run DFS: Loop through all courses. For each UNVISITED course, call DFS. If any DFS call detects a cycle, return False.
5. If no cycles are found: Return True after checking all courses.
Time and Space Complexity
Time Complexity: O(V + E), where V is the number of courses and E is the number of prerequisites. Each node and edge is visited once.
Space Complexity: O(V + E), to store the graph and the visit state.
Why This Works
The key idea is that a valid course schedule corresponds to a Directed Acyclic Graph (DAG). If you can show there is no cycle in the graph formed by prerequisites, then there's some order in which all courses can be taken.
Conclusion
This is a classic graph cycle detection problem disguised in the context of course scheduling. By translating prerequisites into edges and using DFS with a visited state tracker, we can efficiently determine whether a valid schedule exists.