二分图判定

双色球染色 明星和电影的关系

785. 判断二分图 (opens new window)

/**
 * @param {number[][]} graph
 * @return {boolean}
 */
var isBipartite = function (graph) {
  const visible = new Array(graph.length)
  const color = new Array(graph.length).fill(false)
  let ok = true
  const traverse = (graph, s) => {
    // 判断是否被访问过
    if (!ok) {
      return
    }

    // 将当前元素涂成红色

    visible[s] = true

    for (let v of graph[s]) {
      if (visible[v]) {
        if (color[v] === color[s]) {
          ok = false
          return
        }
      } else {
        color[v] = !color[s]
        traverse(graph, v)
      }
    }
  }
  for (let v = 0; v < graph.length; v++) {
    if (!visible[v]) {
      traverse(graph, v)
    }
  }
  return ok
}