-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCourseSchedule.java
More file actions
40 lines (32 loc) · 1.06 KB
/
CourseSchedule.java
File metadata and controls
40 lines (32 loc) · 1.06 KB
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
37
38
39
40
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if(numCourses == 0 || prerequisites.length == 0) return true;
List<ArrayList<Integer>> G = new ArrayList<ArrayList<Integer>>();
int[] indegree = new int[numCourses];
for(int i=0; i < numCourses; i++){
G.add(i, new ArrayList<Integer>());
}
for(int[] pair : prerequisites){
int course = pair[0];
int req = pair[1];
G.get(course).add(req);
indegree[req]++;
}
int cnt = 0;
Queue<Integer> queue = new LinkedList<Integer>();
for(int i=0; i < indegree.length; i++){
if(indegree[i] == 0) queue.offer(i);
}
while(!queue.isEmpty()){
int v = queue.poll();
cnt++;
for(int w : G.get(v)){
indegree[w]--;
if(indegree[w] == 0){
queue.offer(w);
}
}
}
return cnt == numCourses && queue.isEmpty();
}
}