From 3929c18515bc46cae10c0e2d66c0c622591eee96 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sun, 19 Jul 2020 21:31:22 -0500
Subject: Bipartite check done! One of the problems with my code was I ran bfs
 for all vertex, whereas checking just one is enough! Happy I got it done!

---
 src/main/Bipartite.java | 63 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 63 insertions(+)
 create mode 100644 src/main/Bipartite.java

(limited to 'src/main')

diff --git a/src/main/Bipartite.java b/src/main/Bipartite.java
new file mode 100644
index 0000000..d5d72b9
--- /dev/null
+++ b/src/main/Bipartite.java
@@ -0,0 +1,63 @@
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.LinkedList;
+import java.util.Queue;
+import java.util.Scanner;
+
+public class Bipartite {
+    private static int bipartite(ArrayList<Integer>[] adj) {
+
+        boolean bipartiteCheckNodes = bfsBipartiteCheck(adj, 0);
+        if (bipartiteCheckNodes)
+            return 1;
+        else
+            return 0;
+    }
+
+    private static boolean bfsBipartiteCheck(ArrayList<Integer>[] adj, int s) {
+        if (adj[s].size() == 0)
+            return true;
+        int[] dist = new int[adj.length];
+
+        Arrays.fill(dist, -1);
+
+        dist[s] = 0;
+
+        Queue<Integer> vertexQ = new LinkedList<>();
+        vertexQ.add(s);
+
+        while (!vertexQ.isEmpty()) {
+            int u = vertexQ.remove();
+            for (int i : adj[u])
+                if (dist[i] == -1) {
+                    vertexQ.add(i);
+                    if (dist[u] == 0)
+                        dist[i] = 1;
+                    if (dist[u] == 1)
+                        dist[i] = 0;
+                } else if (dist[i] == dist[u]) {
+                    return false;
+                }
+        }
+        return true;
+    }
+
+    public static void main(String[] args) {
+        Scanner scanner = new Scanner(System.in);
+        int n = scanner.nextInt();
+        int m = scanner.nextInt();
+        ArrayList<Integer>[] adj = (ArrayList<Integer>[]) new ArrayList[n];
+        for (int i = 0; i < n; i++) {
+            adj[i] = new ArrayList<Integer>();
+        }
+        for (int i = 0; i < m; i++) {
+            int x, y;
+            x = scanner.nextInt();
+            y = scanner.nextInt();
+            adj[x - 1].add(y - 1);
+            adj[y - 1].add(x - 1);
+        }
+        System.out.println(bipartite(adj));
+    }
+}
+
-- 
cgit v1.2.3