LeetCode Solutions

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

Space: $O(|V|)$

			

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) {
      // Already colored, do nothing
      if (colors[i] != Color::kWhite)
        continue;
      // colors[i] == Color::kWhite
      colors[i] = Color::kRed;  // Always paint w/ Color::kRed
      // BFS
      queue<int> q{{i}};
      while (!q.empty()) {
        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) {
      // Already colored, do nothing
      if (colors[i] != Color.kWhite)
        continue;
      // colors[i] == Color.kWhite
      colors[i] = Color.kRed; // Always paint w/ Color.kRed
      // BFS
      Queue<Integer> q = new ArrayDeque<>(Arrays.asList(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)):
      # Already colored, do nothing
      if colors[i] != Color.kWhite:
        continue
      # colors[i] == Color.kWhite
      colors[i] = Color.kRed  # Always paint w/ Color.kRed
      # BFS
      q = deque([i])
      while 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