diff options
| -rw-r--r-- | 886/main.go | 92 |
1 files changed, 64 insertions, 28 deletions
diff --git a/886/main.go b/886/main.go index 901bf50..d06b3b8 100644 --- a/886/main.go +++ b/886/main.go @@ -2,41 +2,77 @@ 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) +// 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 +// } + +// red: 1; green: -1 +func possibleBipartition(n int, dislikes [][]int) bool { + edges := make([][]int, n+1) + for _, dislike := range dislikes { + u, v := dislike[0], dislike[1] + edges[u] = append(edges[u], v) + edges[v] = append(edges[v], u) } - for i := 1; i <= N; i++ { - if !visited[i] { - visited[i] = true - res := isBiparitionDfs(i, adjList, visited, color) - if !res { + color := make([]int, n+1) + + var dfs func(u, c int) bool + dfs = func(u, c int) bool { + if color[u] != 0 { + return color[u] == c + } + + //fmt.Printf("node: %d will mark color: %d\n", u, c) + color[u] = c + for _, v := range edges[u] { + if !dfs(v, -c) { return false } } - } - return true -} + 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] { + for u := 1; u <= n; u++ { + if color[u] == 0 && !dfs(u, 1) { return false } } |