Leetcode Problem 1136. Parallel Courses

1136. Parallel Courses

Leetcode Solutions

Breadth-First Search (Kahn's Algorithm)

  1. Build a directed graph from relations and record the in-degree of each node.
  2. Initialize a queue and add all nodes with an in-degree of 0 to it.
  3. Initialize step to 0 and visited_count to 0.
  4. While the queue is not empty: a. Increment step. b. For each node in the queue, increment visited_count. c. For each neighbor of the node, decrement its in-degree. d. If a neighbor's in-degree reaches 0, add it to the next queue. e. Update the queue with the next queue.
  5. If visited_count equals the total number of courses, return step. Otherwise, return -1.
UML Thumbnail

Depth-First Search: Check for Cycles + Find Longest Path

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...