DFS Cycle Detection
Intuition
We can model the courses and prerequisites as a directed graph and check whether the graph contains a cycle. If a cycle exists, it is impossible to finish all courses. We perform DFS from each unvisited node, using a three-state coloring scheme: unvisited (white), currently in the DFS stack (gray), and fully processed (black). If during DFS we encounter a gray node, a cycle exists. A node is marked black once all its descendants are fully explored without finding a cycle.
Algorithm
- Build an adjacency list from the prerequisites array, where an edge from `b` to `a` means course `b` is a prerequisite for course `a`.
- Create a state array for each node initialized to "unvisited".
- For each unvisited node, start a DFS traversal.
- Mark the current node as "visiting" (in progress). For each neighbor, if it is "visiting", a cycle is detected -- return false. If it is "unvisited", recurse on it.
- After processing all neighbors, mark the current node as "visited" (complete).
- If no cycle is detected after processing all nodes, return true.
Time
O(V + E) where V is the number of courses and E is the number of prerequisitesSpaceO(V + E) for the adjacency list and recursion stackCode (C++ · Java · Python · Go)
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
for (auto& pre : prerequisites) {
graph[pre[1]].push_back(pre[0]);
}
// 0 = unvisited, 1 = visiting, 2 = visited
vector<int> state(numCourses, 0);
for (int i = 0; i < numCourses; i++) {
if (state[i] == 0 && hasCycle(graph, state, i)) {
return false;
}
}
return true;
}
private:
bool hasCycle(vector<vector<int>>& graph, vector<int>& state, int node) {
state[node] = 1;
for (int neighbor : graph[node]) {
if (state[neighbor] == 1) return true;
if (state[neighbor] == 0 && hasCycle(graph, state, neighbor)) return true;
}
state[node] = 2;
return false;
}
};class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
for (int[] pre : prerequisites) {
graph.get(pre[1]).add(pre[0]);
}
// 0 = unvisited, 1 = visiting, 2 = visited
int[] state = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
if (state[i] == 0 && hasCycle(graph, state, i)) {
return false;
}
}
return true;
}
private boolean hasCycle(List<List<Integer>> graph, int[] state, int node) {
state[node] = 1;
for (int neighbor : graph.get(node)) {
if (state[neighbor] == 1) return true;
if (state[neighbor] == 0 && hasCycle(graph, state, neighbor)) return true;
}
state[node] = 2;
return false;
}
}from typing import List
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = [[] for _ in range(numCourses)]
for a, b in prerequisites:
graph[b].append(a)
# 0 = unvisited, 1 = visiting, 2 = visited
state = [0] * numCourses
def has_cycle(node):
state[node] = 1
for neighbor in graph[node]:
if state[neighbor] == 1:
return True
if state[neighbor] == 0 and has_cycle(neighbor):
return True
state[node] = 2
return False
for i in range(numCourses):
if state[i] == 0 and has_cycle(i):
return False
return Truefunc canFinish(numCourses int, prerequisites [][]int) bool {
graph := make([][]int, numCourses)
for i := range graph {
graph[i] = []int{}
}
for _, pre := range prerequisites {
graph[pre[1]] = append(graph[pre[1]], pre[0])
}
// 0 = unvisited, 1 = visiting, 2 = visited
state := make([]int, numCourses)
var hasCycle func(int) bool
hasCycle = func(node int) bool {
state[node] = 1
for _, neighbor := range graph[node] {
if state[neighbor] == 1 {
return true
}
if state[neighbor] == 0 && hasCycle(neighbor) {
return true
}
}
state[node] = 2
return false
}
for i := 0; i < numCourses; i++ {
if state[i] == 0 && hasCycle(i) {
return false
}
}
return true
}