LeetCode: Is Graph Bipartite Solution

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}/**2 * @param {number[][]} graph3 * @return {boolean}4 */5
6const isValid = function (graph, nodeColors, colorToCheck, node) {7  if (nodeColors[node] !== 0) {8    return nodeColors[node] === colorToCheck9  }10  nodeColors[node] = colorToCheck11  for (const adjacentNode of graph[node]) {12    // this is why using color of 1 and -113    if (!isValid(graph, nodeColors, -colorToCheck, adjacentNode)) {14      return false15    }16  }17  return true18}19
20var isBipartite = function (graph) {21  const N = graph.length22  // 0: no color, 1: blue, -1: red23  const nodeColors = Array(N).fill(0)24
25  // for the case of disconnected graph, check every nodes26  for (let node = 0; node < N; node++) {27    // check if colored yet is equivalent to check if visited yet28    if (nodeColors[node] === 0 && !isValid(graph, nodeColors, 1, node)) {29      return false30    }31  }32
33  return true34}```

leetcode

graph

bfs

dfs

Next Post

LeetCode: Letter Case Permutation

Feb 16, 2021

Search Posts