today's contribution, medium problem, graph bipartation

sherxon · Aug 25, 2018 · 55c3f41 · 55c3f41
1 parent ea58888
commit 55c3f41
Show file tree

Hide file tree

Showing 2 changed files with 76 additions and 0 deletions.
diff --git a/src/problems/Medium.txt b/src/problems/Medium.txt
@@ -2979,3 +2979,35 @@ This tree is also valid:
     1   3
          \
           4
+196)Possible Bipartition
+Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.
+
+Each person may dislike some other people, and they should not go into the same group.
+
+Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.
+
+Return true if and only if it is possible to split everyone into two groups in this way.
+
+
+
+Example 1:
+
+Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
+Output: true
+Explanation: group1 [1,4], group2 [2,3]
+Example 2:
+
+Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
+Output: false
+Example 3:
+
+Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
+Output: false
+
+Note:
+
+1 <= N <= 2000
+0 <= dislikes.length <= 10000
+1 <= dislikes[i][j] <= N
+dislikes[i][0] < dislikes[i][1]
+There does not exist i != j for which dislikes[i] == dislikes[j].
diff --git a/src/problems/medium/PossibleBipartition.java b/src/problems/medium/PossibleBipartition.java
@@ -0,0 +1,44 @@
+package problems.medium;
+
+import java.util.*;
+
+/**
+ * Why Did you create this class? what does it do?
+ */
+public class PossibleBipartition {
+    public boolean possibleBipartition(int n, int[][] dislikes) {
+        Map<Integer, Boolean> bools = new HashMap<>();
+        Map<Integer, Set<Integer>> map = new HashMap<>();
+        for (int i = 0; i < dislikes.length; i++) {
+            int ii = dislikes[i][0];
+            int jj = dislikes[i][1];
+            Set<Integer> set = map.getOrDefault(ii, new HashSet<>());
+            set.add(jj);
+            map.put(ii, set);
+            set = map.getOrDefault(jj, new HashSet<>());
+            set.add(ii);
+            map.put(jj, set);
+        }
+        bools.put(1, true);
+        Queue<Integer> q = new LinkedList<>();
+        Set<Integer> visited = new HashSet<>();
+        q.add(1);
+        while (!q.isEmpty()) {
+            Integer current = q.remove();
+            visited.add(current);
+            if (map.get(current) != null) {
+                for (Integer nei : map.get(current)) {
+                    if (!visited.contains(nei)) {
+                        if (bools.get(nei) == bools.get(current)) {
+                            return false;
+                        }
+                        q.add(nei);
+                        bools.put(nei, !bools.get(current));
+                    }
+                }
+            }
+        }
+        return true;
+
+    }
+}