|
1 | 1 | classSolution { |
2 | | -publicbooleancanFinish(intnumCourses,int[][]prerequisites) { |
3 | | -Map<Integer,Set<Integer>>map =newHashMap<>(); |
4 | | -int[]indegree =newint[numCourses]; |
5 | | -for (int[]prerequisite :prerequisites) { |
6 | | -map.computeIfAbsent(prerequisite[1],k ->newHashSet<>()).add(prerequisite[0]); |
7 | | -indegree[prerequisite[0]]++; |
8 | | - } |
9 | | -Queue<Integer>queue =newLinkedList<>(); |
10 | | -Set<Integer>taken =newHashSet<>(); |
11 | | -for (inti =0;i <numCourses;i++) { |
12 | | -if (indegree[i] ==0) { |
13 | | -queue.add(i); |
14 | | -taken.add(i); |
15 | | - } |
16 | | - } |
17 | | -while (!queue.isEmpty()) { |
18 | | -intremoved =queue.remove(); |
19 | | -for (IntegerdependentCourse :map.getOrDefault(removed,newHashSet<>())) { |
20 | | -indegree[dependentCourse]--; |
21 | | -if (indegree[dependentCourse] ==0) { |
22 | | -taken.add(dependentCourse); |
23 | | -queue.add(dependentCourse); |
| 2 | +publicbooleancanFinish(intnumCourses,int[][]prerequisites) { |
| 3 | +int[]indegree =newint[numCourses]; |
| 4 | +Map<Integer,Set<Integer>>map =newHashMap<>(); |
| 5 | +for (int[]prerequisite :prerequisites) { |
| 6 | +intcourse =prerequisite[0]; |
| 7 | +intprereq =prerequisite[1]; |
| 8 | +indegree[course]++; |
| 9 | +map.computeIfAbsent(prereq,k ->newHashSet<>()).add(course); |
| 10 | + } |
| 11 | +Queue<Integer>queue =newLinkedList<>(); |
| 12 | +Set<Integer>visited =newHashSet<>(); |
| 13 | +for (inti =0;i <numCourses;i++) { |
| 14 | +if (indegree[i] ==0) { |
| 15 | +queue.add(i); |
| 16 | +visited.add(i); |
| 17 | + } |
| 18 | + } |
| 19 | +while (!queue.isEmpty()) { |
| 20 | +intremoved =queue.remove(); |
| 21 | +for (Integerconn :map.getOrDefault(removed,newHashSet<>())) { |
| 22 | +indegree[conn]--; |
| 23 | +if (indegree[conn] ==0) { |
| 24 | +queue.add(conn); |
| 25 | +visited.add(conn); |
| 26 | + } |
| 27 | + } |
24 | 28 | } |
25 | | -} |
| 29 | +returnvisited.size() ==numCourses; |
26 | 30 | } |
27 | | -returntaken.size() ==numCourses; |
28 | | - } |
29 | 31 | } |