aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--886/go.mod3
-rw-r--r--886/main.go50
2 files changed, 53 insertions, 0 deletions
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}}))
+}