785. Is Graph Bipartite?

Approach 1: BFS

• Time: $O(|V| + |E|)$
• Space: $O(|V|)$

C++JavaPython

enum class Color { kWhite, kRed, kGreen };

class Solution {
 public:
  bool isBipartite(vector<vector<int>>& graph) {
    vector<Color> colors(graph.size(), Color::kWhite);

    for (int i = 0; i < graph.size(); ++i) {
      // This node has been colored, so do nothing.
      if (colors[i] != Color::kWhite)
        continue;
      // Always paint red for a white node.
      colors[i] = Color::kRed;
      // BFS.
      queue<int> q{{i}};
      while (!q.empty())
        for (int sz = q.size(); sz > 0; --sz) {
          const int u = q.front();
          q.pop();
          for (const int v : graph[u]) {
            if (colors[v] == colors[u])
              return false;
            if (colors[v] == Color::kWhite) {
              colors[v] =
                  colors[u] == Color::kRed ? Color::kGreen : Color::kRed;
              q.push(v);
            }
          }
        }
    }

    return true;
  }
};

enum Color { kWhite, kRed, kGreen }

class Solution {
  public boolean isBipartite(int[][] graph) {
    Color[] colors = new Color[graph.length];
    Arrays.fill(colors, Color.kWhite);

    for (int i = 0; i < graph.length; ++i) {
      // This node has been colored, so do nothing.
      if (colors[i] != Color.kWhite)
        continue;
      // Always paint red for a white node.
      colors[i] = Color.kRed;
      // BFS.
      Queue<Integer> q = new ArrayDeque<>(List.of(i));
      while (!q.isEmpty())
        for (int sz = q.size(); sz > 0; --sz) {
          final int u = q.poll();
          for (final int v : graph[u]) {
            if (colors[v] == colors[u])
              return false;
            if (colors[v] == Color.kWhite) {
              colors[v] = colors[u] == Color.kRed ? Color.kGreen : Color.kRed;
              q.offer(v);
            }
          }
        }
    }

    return true;
  }
}

from enum import Enum


class Color(Enum):
  kWhite = 0
  kRed = 1
  kGreen = 2


class Solution:
  def isBipartite(self, graph: list[list[int]]) -> bool:
    colors = [Color.kWhite] * len(graph)

    for i in range(len(graph)):
      # This node has been colored, so do nothing.
      if colors[i] != Color.kWhite:
        continue
      # Always paint red for a white node.
      colors[i] = Color.kRed
      # BFS.
      q = collections.deque([i])
      while q:
        for _ in range(len(q)):
          u = q.popleft()
          for v in graph[u]:
            if colors[v] == colors[u]:
              return False
            if colors[v] == Color.kWhite:
              colors[v] = Color.kRed if colors[u] == Color.kGreen else Color.kGreen
              q.append(v)

    return True

Approach 2: DFS

• Time: $O(|V| + |E|)$
• Space: $O(|V|)$

C++JavaPython

enum class Color { kWhite, kRed, kGreen };

class Solution {
 public:
  bool isBipartite(vector<vector<int>>& graph) {
    vector<Color> colors(graph.size(), Color::kWhite);

    for (int i = 0; i < graph.size(); ++i)
      if (colors[i] == Color::kWhite &&
          !isValidColor(graph, i, colors, Color::kRed))
        return false;

    return true;
  }

 private:
  bool isValidColor(const vector<vector<int>>& graph, int u,
                    vector<Color>& colors, Color color) {
    // The painted color should be same as `color`.
    if (colors[u] != Color::kWhite)
      return colors[u] == color;

    colors[u] = Color::kRed;

    // All the children should have valid colors.
    for (const int v : graph[u])
      if (!isValidColor(graph, v, colors,
                        color == Color::kRed ? Color::kGreen : Color::kRed))
        return false;

    return true;
  }
};

enum Color { kWhite, kRed, kGreen }

class Solution {
  public boolean isBipartite(int[][] graph) {
    Color[] colors = new Color[graph.length];
    Arrays.fill(colors, Color.kWhite);

    for (int i = 0; i < graph.length; ++i)
      if (colors[i] == Color.kWhite && !isValidColor(graph, i, colors, Color.kRed))
        return false;

    return true;
  }

  private boolean isValidColor(int[][] graph, int u, Color[] colors, Color color) {
    // The painted color should be same as `color`.
    if (colors[u] != Color.kWhite)
      return colors[u] == color;

    colors[u] = color;

    // All the children should have valid colors.
    for (final int v : graph[u])
      if (!isValidColor(graph, v, colors, color == Color.kRed ? Color.kGreen : Color.kRed))
        return false;

    return true;
  }
}

from enum import Enum


class Color(Enum):
  kWhite = 0
  kRed = 1
  kGreen = 2


class Solution:
  def isBipartite(self, graph: list[list[int]]) -> bool:
    colors = [Color.kWhite] * len(graph)

    def isValidColor(u: int, color: Color) -> bool:
      # The painted color should be same as `color`.
      if colors[u] != Color.kWhite:
        return colors[u] == color

      colors[u] = color

      # All the children should have valid colors.
      childrenColor = Color.kRed if colors[u] == Color.kGreen else Color.kGreen
      return all(isValidColor(v, childrenColor) for v in graph[u])

    return all(colors[i] != Color.kWhite or isValidColor(i, Color.kRed)
               for i in range(len(graph)))