Leetcode Problem 207. Course Schedule

207. Course Schedule

Leetcode Solutions

Approach: Topological Sort Using Kahn's Algorithm

  1. Initialize an array indegree to store the number of incoming edges for each node.
  2. Create an adjacency list adj to store outgoing edges from each node.
  3. Populate indegree and adj using the prerequisites array.
  4. Initialize a queue q and add all nodes with an indegree of zero.
  5. Initialize nodesVisited to count the number of processed nodes.
  6. While q is not empty: a. Dequeue a node from q and increment nodesVisited. b. For each neighbor of the dequeued node, decrement its indegree. c. If a neighbor's indegree becomes zero, enqueue it.
  7. Return true if nodesVisited equals numCourses, indicating no cycle; otherwise, return false.
UML Thumbnail

Approach: Depth First Search for Cycle Detection

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...