There are n courses and prerequisites (u must be taken before v). Find minimum semesters to complete all courses. Return -1 if impossible (cycle).
Input: n=3, relations=[[1,3],[2,3]] → Output: 2Input: n=3, relations=[[1,2],[2,3],[3,1]] → Output: -1
Topological sort with BFS (Kahn's). Track depth (semester) of each node. If not all nodes processed, there is a cycle.
- Build adjacency list and in-degree array.
- BFS from all nodes with in-degree 0.
- Each BFS level = one semester. Decrement in-degrees of neighbors; add to queue when in-degree becomes 0.
- If total processed < n: return -1 (cycle). Else return levels.
import java.util.*;
class Solution {
public int minimumSemesters(int n, int[][] relations) {
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[n+1];
for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
for (int[] r : relations) { graph.get(r[0]).add(r[1]); inDegree[r[1]]++; }
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= n; i++) if (inDegree[i] == 0) q.offer(i);
int semesters = 0, studied = 0;
while (!q.isEmpty()) {
semesters++;
int size = q.size(); studied += size;
for (int i = 0; i < size; i++) {
int u = q.poll();
for (int v : graph.get(u)) if (--inDegree[v] == 0) q.offer(v);
}
}
return studied == n ? semesters : -1;
}
}
- Time Complexity: O(V+E)
- Space Complexity: O(V+E)