## Approach 1: BFS

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

## C++

``````enum class Color { WHITE, RED, GREEN };

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

for (int i = 0; i < graph.size(); ++i) {
if (colors[i] != Color::WHITE)
continue;
// colors[i] == Color::WHITE
colors[i] = Color::RED;  // always paint w/ Color::RED
// 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::WHITE) {
colors[v] = colors[u] == Color::RED ? Color::GREEN : Color::RED;
q.push(v);
}
}
}
}

return true;
}
};
``````

## JAVA

``````enum Color { WHITE, RED, GREEN }

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

for (int i = 0; i < graph.length; ++i) {
if (colors[i] != Color.WHITE)
continue;
// colors[i] == Color.WHITE
colors[i] = Color.RED; // always paint w/ Color.RED
// 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.WHITE) {
colors[v] = colors[u] == Color.RED ? Color.GREEN : Color.RED;
q.offer(v);
}
}
}
}
}

return true;
}
}
``````

## Python

``````from enum import Enum

class Color(Enum):
WHITE = 0
RED = 1
GREEN = 2

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

for i in range(len(graph)):
if colors[i] != Color.WHITE:
continue
# colors[i] == Color.WHITE
colors[i] = Color.RED  # always paint w/ Color.RED
# 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.WHITE:
colors[v] = Color.RED if colors[u] == Color.GREEN else Color.GREEN
q.append(v)

return True
``````

## Approach 2: DFS

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

## C++

``````enum class Color { WHITE, RED, GREEN };

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

for (int i = 0; i < graph.size(); ++i)
if (colors[i] == Color::WHITE &&
!isValidColor(graph, i, colors, Color::RED))
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 the `color`
if (colors[u] != Color::WHITE)
return colors[u] == color;

colors[u] = color;  // always paint w/ `color`

// all children should have valid colors
for (const int v : graph[u])
if (!isValidColor(graph, v, colors,
color == Color::RED ? Color::GREEN : Color::RED))
return false;

return true;
}
};
``````

## JAVA

``````enum Color { WHITE, RED, GREEN }

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

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

return true;
}

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

colors[u] = color; // always paint w/ `color`

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

return true;
}
}
``````

## Python

``````from enum import Enum

class Color(Enum):
WHITE = 0
RED = 1
GREEN = 2

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

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

colors[u] = color  # always paint w/ `color`

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

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