785.判断二分图

链接：785.判断二分图
难度：Medium
标签：深度优先搜索、广度优先搜索、并查集、图
简介：给定一个无向图 graph，当这个图为二分图时返回 true。

题解 1 - typescript

• 编辑时间：2020-07-16
• 执行用时：84ms
• 内存消耗：38MB
• 编程语言：typescript
• 解法介绍：遍历后采取红绿刷色。

function isBipartite(graph: number[][]): boolean {
  enum Color {
    red,
    green,
    none,
  }
  const len = graph.length;
  let valid = true;
  const colors = new Array<Color>(len).fill(Color.none);
  for (let i = 0; i < len && valid; i++) {
    colors[i] === Color.none && dfs(i, Color.red);
  }
  return valid;
  function dfs(node: number, color: Color): void {
    colors[node] = color;
    const newColor = color === Color.red ? Color.green : Color.red;
    for (const neighbor of graph[node]) {
      if (colors[neighbor] === Color.none) {
        dfs(neighbor, newColor);
        if (!valid) return;
      } else if (colors[neighbor] !== newColor) {
        valid = false;
        return;
      }
    }
  }
}