Added 2 solutions

varunu28 · varunu28 · commit 3cf75a166b92 · 2019-07-31T07:46:09.000-07:00
diff --git a/Hard/Parallel Courses.java b/Hard/Parallel Courses.java
@@ -0,0 +1,46 @@
+class Solution {
+    public int minimumSemesters(int N, int[][] relations) {
+        Map<Integer, List<Integer>> map = new HashMap<>();
+        // A prerequisite counter for each course
+        int[] prereqs = new int[N + 1];
+        
+        for (int[] relation : relations) {
+            map.computeIfAbsent(relation[0], k-> new ArrayList<>()).add(relation[1]);
+            prereqs[relation[1]]++;
+        }
+        
+        Queue<Integer> queue = new LinkedList<>();
+        
+        // Add all the courses which have no prerequisite
+        // So that we can take those courses in first semester
+        for (int i = 1; i <= N; i++) {
+            if (prereqs[i] == 0) {
+                queue.add(i);
+            }
+        }
+        
+        int semester = 0;
+        while (!queue.isEmpty()) {
+            int size = queue.size();
+            while (size-- > 0) {
+                int course = queue.poll();
+                // Decrement N as we have taken a course that is removed from the queue
+                N--;
+                for (int pre : map.getOrDefault(course, new ArrayList<>())) {
+                    /*
+                    If a course which depends upon the removed course had only the removed course as prereq then we can
+                    add it to the queue
+                    */
+                    if (--prereqs[pre] == 0) {
+                        queue.add(pre);
+                    }
+                }
+            }
+            
+            // Semester over. New semester starts
+            semester++;
+        }
+
+        return N == 0 ? semester : -1;
+    }
+}
diff --git a/Medium/Is Graph Bipartite.java b/Medium/Is Graph Bipartite.java
@@ -0,0 +1,29 @@
+class Solution {
+    public boolean isBipartite(int[][] graph) {
+        int[] colors = new int[graph.length];
+        Arrays.fill(colors, -1);
+        Stack<Integer> stack = new Stack<>();
+        
+        for (int i = 0; i < graph.length; i++) {
+            if (colors[i] == -1) {
+                stack.push(i);
+                colors[i] = 0;
+                
+                while (!stack.isEmpty()) {
+                    Integer removed = stack.pop();
+                    for (Integer connect : graph[removed]) {
+                        if (colors[connect] == -1) {
+                            stack.push(connect);
+                            colors[connect] = colors[removed] == 1 ? 0 : 1;
+                        }
+                        else if (colors[connect] == colors[removed]) {
+                            return false;
+                        }
+                    }
+                }
+            }
+        }
+        
+        return true;
+    }
+}
