forked from mdabarik/blind-75-leetcode-questions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
28--course-schedule.java
36 lines (35 loc) · 1.17 KB
/
28--course-schedule.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : prerequisites) {
adj.get(edge[1]).add(edge[0]);
}
int[] indegree = new int[numCourses];
for (int[] edge : prerequisites) {
indegree[edge[0]]++;
}
int enrolled = 0;
Queue<Integer> queue = new LinkedList<>();
for (int node = 0; node < indegree.length; node++) {
if (indegree[node] == 0) {
queue.add(node);
enrolled++;
}
}
while (!queue.isEmpty()) {
int currNode = queue.poll(); // current course
for (int neighbor : adj.get(currNode)) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) {
queue.add(neighbor);
enrolled++;
}
}
}
return (numCourses == enrolled);
}
} // TC: O(V + E), SC: O(V)
/* [[0,4],[0,5],[1,4],[2,5],[1,3],[3,2]], 6 */