_1136.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.HashSet;
importjava.util.LinkedList;
importjava.util.List;
importjava.util.Map;
importjava.util.Queue;
importjava.util.Set;

publicclass_1136 {
publicstaticclassSolution1 {
publicintminimumSemesters(intn, int[][] relations) {
Map<Integer, Set<Integer>> indegree = newHashMap<>();
for (int[] rel : relations) {
if (!indegree.containsKey(rel[1])) {
indegree.put(rel[1], newHashSet<>());
 }
Set<Integer> prereqs = indegree.get(rel[1]);
prereqs.add(rel[0]);
 }
Queue<Integer> queue = newLinkedList<>();
Set<Integer> taken = newHashSet<>();
for (inti = 1; i <= n; i++) {
if (!indegree.containsKey(i)) {
queue.offer(i);
taken.add(i);
 }
 }
intminSemesters = 0;
while (!queue.isEmpty()) {
intsize = queue.size();
minSemesters++;
for (inti = 0; i < size; i++) {
Integercurr = queue.poll();
for (intkey : indegree.keySet()) {
Set<Integer> prereqs = indegree.get(key);
if (prereqs.contains(curr)) {
prereqs.remove(curr);
if (prereqs.size() == 0) {
queue.offer(key);
taken.add(key);
 }
 }
 }
 }
 }
returntaken.size() != n ? -1 : minSemesters;
 }
 }

publicstaticclassSolution2 {
/*
 * A straightforward one to practice topological sort (template).
 * Use an indegree/outdegree array and an array of list type.
 */

publicintminimumSemesters(intn, int[][] relations) {
List<Integer>[] adjList = newArrayList[n + 1];
for (inti = 1; i <= n; i++) {
adjList[i] = newArrayList<>();
 }
int[] indegree = newint[n + 1];
for (int[] rel : relations) {
indegree[rel[1]]++;
adjList[rel[0]].add(rel[1]);
 }
Queue<Integer> q = newLinkedList<>();
for (inti = 1; i <= n; i++) {
if (indegree[i] == 0) {
q.offer(i);
 }
 }
intsemesters = 0;
while (!q.isEmpty()) {
intsize = q.size();
for (inti = 0; i < size; i++) {
Integercurr = q.poll();
for (intv : adjList[curr]) {
indegree[v]--;
if (indegree[v] == 0) {
q.offer(v);
 }
 }
 }
semesters++;
 }
for (inti = 1; i <= n; i++) {
if (indegree[i] != 0) {
return -1;
 }
 }
returnsemesters;
 }
 }
}