From 5b26828c2e367bfebf24894081c3e558eb1c3315 Mon Sep 17 00:00:00 2001
From: terminaldweller <thabogre@gmail.com>
Date: Wed, 21 Dec 2022 09:30:16 +0330
Subject: 886

---
 886/go.mod  |  3 +++
 886/main.go | 50 ++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 53 insertions(+)
 create mode 100644 886/go.mod
 create mode 100644 886/main.go

diff --git a/886/go.mod b/886/go.mod
new file mode 100644
index 0000000..782c007
--- /dev/null
+++ b/886/go.mod
@@ -0,0 +1,3 @@
+module 886
+
+go 1.19
diff --git a/886/main.go b/886/main.go
new file mode 100644
index 0000000..901bf50
--- /dev/null
+++ b/886/main.go
@@ -0,0 +1,50 @@
+package main
+
+import "fmt"
+
+func possibleBipartition(N int, dislikes [][]int) bool {
+	color := make(map[int]bool, N)
+	visited := make(map[int]bool, N)
+	adjList := make(map[int][]int, N)
+
+	for _, d := range dislikes {
+		a := d[0]
+		b := d[1]
+		adjList[a] = append(adjList[a], b)
+		adjList[b] = append(adjList[b], a)
+	}
+
+	for i := 1; i <= N; i++ {
+		if !visited[i] {
+			visited[i] = true
+			res := isBiparitionDfs(i, adjList, visited, color)
+			if !res {
+				return false
+			}
+		}
+	}
+
+	return true
+}
+
+func isBiparitionDfs(cur int, adjList map[int][]int, visited map[int]bool, color map[int]bool) bool {
+	for _, next := range adjList[cur] {
+		if !visited[next] {
+			visited[next] = true
+			color[next] = !color[cur]
+			res := isBiparitionDfs(next, adjList, visited, color)
+			if !res {
+				return false
+			}
+		} else if color[cur] == color[next] {
+			return false
+		}
+	}
+	return true
+}
+
+func main() {
+	fmt.Println(possibleBipartition(4, [][]int{{1, 2}, {1, 3}, {2, 4}}))
+	fmt.Println(possibleBipartition(3, [][]int{{1, 2}, {1, 3}, {2, 3}}))
+	fmt.Println(possibleBipartition(5, [][]int{{1, 2}, {2, 3}, {3, 4}, {4, 5}, {1, 5}}))
+}
-- 
cgit v1.2.3