diff options
author | terminaldweller <thabogre@gmail.com> | 2022-12-21 06:00:16 +0000 |
---|---|---|
committer | terminaldweller <thabogre@gmail.com> | 2022-12-21 06:00:16 +0000 |
commit | 5b26828c2e367bfebf24894081c3e558eb1c3315 (patch) | |
tree | 31887159b43dd72c9e6186679c29454494a54ac9 /886 | |
parent | 841 (diff) | |
download | leetcode-5b26828c2e367bfebf24894081c3e558eb1c3315.tar.gz leetcode-5b26828c2e367bfebf24894081c3e558eb1c3315.zip |
886
Diffstat (limited to '886')
-rw-r--r-- | 886/go.mod | 3 | ||||
-rw-r--r-- | 886/main.go | 50 |
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}})) +} |