Problem
Given numCourses and prerequisites pairs [a, b] meaning b must be taken before a, return true if you can finish all courses.
Example
Input: numCourses = 2, prerequisites = [[1,0]]
Output: trueSolution
Detect a cycle in the directed graph using DFS with three colors (white, gray, black).
def can_finish(num_courses, prerequisites):
graph = [[] for _ in range(num_courses)]
for a, b in prerequisites:
graph[b].append(a)
state = [0] * num_courses
def dfs(node):
if state[node] == 1: return False
if state[node] == 2: return True
state[node] = 1
for nei in graph[node]:
if not dfs(nei): return False
state[node] = 2
return True
return all(dfs(i) for i in range(num_courses))function canFinish(n, pre) {
const graph = Array.from({length: n}, () => []);
for (const [a, b] of pre) graph[b].push(a);
const state = new Array(n).fill(0);
function dfs(node) {
if (state[node] === 1) return false;
if (state[node] === 2) return true;
state[node] = 1;
for (const nei of graph[node]) if (!dfs(nei)) return false;
state[node] = 2;
return true;
}
for (let i = 0; i < n; i++) if (!dfs(i)) return false;
return true;
}bool dfs(int node, vector<vector<int>>& g, vector<int>& state) {
if (state[node] == 1) return false;
if (state[node] == 2) return true;
state[node] = 1;
for (int nei : g[node]) if (!dfs(nei, g, state)) return false;
state[node] = 2;
return true;
}
bool canFinish(int n, vector<vector<int>>& pre) {
vector<vector<int>> g(n);
for (auto& p : pre) g[p[1]].push_back(p[0]);
vector<int> state(n, 0);
for (int i = 0; i < n; i++) if (!dfs(i, g, state)) return false;
return true;
}public boolean canFinish(int n, int[][] pre) {
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] p : pre) g.get(p[1]).add(p[0]);
int[] state = new int[n];
for (int i = 0; i < n; i++) if (!dfs(i, g, state)) return false;
return true;
}
private boolean dfs(int node, List<List<Integer>> g, int[] state) {
if (state[node] == 1) return false;
if (state[node] == 2) return true;
state[node] = 1;
for (int nei : g.get(node)) if (!dfs(nei, g, state)) return false;
state[node] = 2;
return true;
}Complexity
- Time: O(V + E)
- Space: O(V + E)
Explanation
State 0 = unvisited, 1 = in current DFS path, 2 = fully processed. If we hit a node in state 1, we found a cycle.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?