mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 16:36:41 +08:00
36 lines
667 B
Go
36 lines
667 B
Go
package leetcode
|
||
|
||
// DFS 染色，1 是红色，0 是绿色，-1 是未染色
|
||
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) {
|
||
return false
|
||
}
|
||
}
|
||
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 {
|
||
return false
|
||
} else if colors[n] != parentCol {
|
||
return true
|
||
}
|
||
for _, c := range graph[n] {
|
||
if !dfs(c, graph, colors, colors[n]) {
|
||
return false
|
||
}
|
||
}
|
||
return true
|
||
}
|