LeetCode 1136 Parallel Courses - Example and Complexity Analysis

Trace n = 4, relations = [[2,1],[3,1],[4,2],[4,3]].

Graph: 1 → 2 → 4, 1 → 3 → 4. In-degrees: 1:0, 2:1, 3:1, 4:2.

Semester 1: process [1]. Decrement neighbors. In-degrees: 2:0, 3:0, 4:2.

Semester 2: process [2, 3]. Decrement: 4:0.

Semester 3: process [4].

Total: 3 semesters. This is the length of the longest chain: 1 → 2 → 4 or 1 → 3 → 4.

$O(V + E)$ time for BFS. $O(V + E)$ space for graph and queue.