785.Is Graph Bipartite?

DwivediAman-exe · web-flow · commit e85635e6f945 · 2020-10-04T15:38:27.000+05:30
Adding a new solution,
Leetcode Q.785 solution in Go lang using Depth First Search,
faster than 100 % ( 20ms ) with a memory usage of 12 MB.
diff --git a/leetcode/785.Is Graph Bipartite? b/leetcode/785.Is Graph Bipartite?
@@ -0,0 +1,44 @@
+func isBipartite(graph [][]int) bool {
+    colors := make([]int,len(graph))
+    
+    
+    for i := range colors {
+        colors[i] = -1
+    }
+
+    
+    for i := range graph {
+        if !dfs(i, graph, colors, -1) {
+            fmt.Println(colors)
+            return false
+        }
+    }
+    
+    fmt.Println(colors)
+    return true
+    
+}
+
+func dfs(n int, graph [][]int, colors []int, parentCol int) bool {
+    if colors[n] == -1 {
+        if parentCol == 1 {
+            colors[n] = 0
+        } else {
+            colors[n] = 1 
+        }
+    } else if colors[n] == parentCol {
+        fmt.Println(n)
+        return false
+    } else if colors[n] != parentCol {
+        return true
+    }
+    
+    
+    for _, c := range graph[n] {
+        if !dfs(c, graph, colors, colors[n]) {
+            fmt.Println(c)
+            return false
+        }
+    }
+    return true
+}
