Check if it is possible to finish all task from given dependencies (Course Schedule I) Medium 0 attempts
GeeksforGeeks ↗

Check if it is possible to finish all task from given dependencies (Course Schedule I)

Medium GraphBFSDFS GeeksforGeeks

You have numCourses courses, and a list of prerequisite pairs where [a, b] means course b must be completed before course a. Decide whether it's possible to finish every course — equivalently, check whether the prerequisite graph contains a cycle.

Input Format
Implement canFinish(numCourses, prerequisites). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
numCourses = 2
prerequisites = [[1,0]]
Output
true

Example 2

Input
numCourses = 2
prerequisites = [[1,0],[0,1]]
Output
false
Constraints
  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
Test Cases (2)
Case 1
Args: [2,[[1,0]]] Expected: true
Case 2
Args: [2,[[1,0],[0,1]]] Expected: false
Topics
GraphBFSDFS

Topological Sort (Kahn's Algorithm)

If we can process all courses via BFS topological sort, there's no cycle.

javascript
function canFinish(numCourses, prerequisites) {
  const graph = Array.from({length: numCourses}, () => []);
  const inDeg = Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) { graph[b].push(a); inDeg[a]++; }
  const q = [];
  for (let i = 0; i < numCourses; i++) if (inDeg[i] === 0) q.push(i);
  let count = 0;
  let head = 0;
  while (head < q.length) {
    const node = q[head++]; count++;
    for (const next of graph[node]) { if (--inDeg[next] === 0) q.push(next); }
  }
  return count === numCourses;
}

Time: O(V + E) | Space: O(V + E)

Saved in this browser only. Private to you.

JavaScript