|
1 | 1 | classSolution { |
2 | | -publicintminimumSemesters(intn,int[][]relations) { |
3 | | -Map<Integer,List<Integer>>graph =newHashMap<>(); |
4 | | -int[]indegree =newint[n +1]; |
5 | | -for (int[]relation :relations) { |
6 | | -graph.computeIfAbsent(relation[0],k ->newArrayList<>()).add(relation[1]); |
7 | | -indegree[relation[1]]++; |
8 | | - } |
9 | | -Queue<Integer>queue =newLinkedList<>(); |
10 | | -intnumOfSemesters =0; |
11 | | -Set<Integer>coursesTaken =newHashSet<>(); |
12 | | -for (inti =1;i <=n;i++) { |
13 | | -if (indegree[i] ==0) { |
14 | | -queue.add(i); |
15 | | - } |
16 | | - } |
17 | | -while (!queue.isEmpty()) { |
18 | | -intsize =queue.size(); |
19 | | -while (size-- >0) { |
20 | | -intcourse =queue.remove(); |
21 | | -coursesTaken.add(course); |
22 | | -for (intdependentCourse :graph.getOrDefault(course,newArrayList<>())) { |
23 | | -indegree[dependentCourse]--; |
24 | | -if (indegree[dependentCourse] <=0 && !coursesTaken.contains(dependentCourse)) { |
25 | | -queue.add(dependentCourse); |
26 | | - } |
| 2 | +publicintminimumSemesters(intn,int[][]relations) { |
| 3 | +Map<Integer,Set<Integer>>graph =newHashMap<>(); |
| 4 | +int[]indegree =newint[n]; |
| 5 | +for (int[]relation :relations) { |
| 6 | +intcourse =relation[0]; |
| 7 | +intdependency =relation[1]; |
| 8 | +indegree[course -1]++; |
| 9 | +graph.computeIfAbsent(dependency,k ->newHashSet<>()).add(course); |
| 10 | + } |
| 11 | +Queue<Integer>queue =newLinkedList<>(); |
| 12 | +intnumOfSemesters =0; |
| 13 | +intcoursesTaken =0; |
| 14 | +for (inti =0;i <n;i++) { |
| 15 | +if (indegree[i] ==0) { |
| 16 | +queue.add(i +1); |
| 17 | + } |
| 18 | + } |
| 19 | +while (!queue.isEmpty()) { |
| 20 | +intsize =queue.size(); |
| 21 | +while (size-- >0) { |
| 22 | +intremoved =queue.remove(); |
| 23 | +coursesTaken++; |
| 24 | +for (Integerdependent :graph.getOrDefault(removed,newHashSet<>())) { |
| 25 | +indegree[dependent -1]--; |
| 26 | +if (indegree[dependent -1] ==0) { |
| 27 | +queue.add(dependent); |
| 28 | + } |
| 29 | + } |
| 30 | + } |
| 31 | +numOfSemesters++; |
27 | 32 | } |
28 | | - } |
29 | | -numOfSemesters++; |
| 33 | +returncoursesTaken ==n ?numOfSemesters : -1; |
30 | 34 | } |
31 | | -returncoursesTaken.size() ==n ?numOfSemesters : -1; |
32 | | - } |
33 | 35 | } |