LeetCode: Is Graph Bipartite Solution

1/**
2 * @param {number[][]} graph
3 * @return {boolean}
4 */
5
6const isValid = function (graph, nodeColors, colorToCheck, node) {
7  if (nodeColors[node] !== 0) {
8    return nodeColors[node] === colorToCheck
9  }
10  nodeColors[node] = colorToCheck
11  for (const adjacentNode of graph[node]) {
12    // this is why using color of 1 and -1
13    if (!isValid(graph, nodeColors, -colorToCheck, adjacentNode)) {
14      return false
15    }
16  }
17  return true
18}
19
20var isBipartite = function (graph) {
21  const N = graph.length
22  // 0: no color, 1: blue, -1: red
23  const nodeColors = Array(N).fill(0)
24
25  // for the case of disconnected graph, check every nodes
26  for (let node = 0; node < N; node++) {
27    // check if colored yet is equivalent to check if visited yet
28    if (nodeColors[node] === 0 && !isValid(graph, nodeColors, 1, node)) {
29      return false
30    }
31  }
32
33  return true
34}