Is Graph Bipartite?
Is Graph Bipartite? is a medium graphs problem solved with the cycle detection pattern.
The best approach, dfs two-colouring, runs in O(V + E) time and O(V) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from bfs two-colouring up.
Problem
An undirected graph is bipartite if its nodes can be split into two groups so that every edge connects nodes from different groups. graph[u] lists the neighbours of u. Decide whether the graph is bipartite.
Examples
Example 1
- Input
graph = [[1,3],[0,2],[1,3],[0,2]]- Output
true- Why
- Sets {0, 2} and {1, 3}.
Example 2
- Input
graph = [[1,2,3],[0,2],[0,1,3],[0,2]]- Output
false- Why
- 0, 1, 2 form a triangle, which is an odd cycle.
Constraints
1 <= n <= 100; undirected, possibly disconnected.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| BFS two-colouring | O(V + E) | O(V) |
| DFS two-colouring | O(V + E) | O(V) |
1BFS two-colouring
O(V + E)O(V)Colour an uncoloured node 0, then give every neighbour the opposite colour with BFS. A neighbour with the same colour means the graph is not bipartite.
- color[] = -1.
- For each uncoloured start: BFS; neighbour uncoloured → 1 - color[u]; same colour → false.
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] color = new int[n];
Arrays.fill(color, -1);
for (int s = 0; s < n; s++) {
if (color[s] != -1) continue;
Queue<Integer> q = new ArrayDeque<>();
q.add(s);
color[s] = 0;
while (!q.isEmpty()) {
int u = q.poll();
for (int v : graph[u]) {
if (color[v] == -1) { color[v] = 1 - color[u]; q.add(v); }
else if (color[v] == color[u]) return false;
}
}
}
return true;
}
}class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
n = len(graph)
color = [-1] * n
for s in range(n):
if color[s] != -1:
continue
q = deque([s])
color[s] = 0
while q:
u = q.popleft()
for v in graph[u]:
if color[v] == -1:
color[v] = 1 - color[u]
q.append(v)
elif color[v] == color[u]:
return False
return Trueclass Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> color(n, -1);
for (int s = 0; s < n; s++) {
if (color[s] != -1) continue;
queue<int> q;
q.push(s);
color[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (color[v] == -1) { color[v] = 1 - color[u]; q.push(v); }
else if (color[v] == color[u]) return false;
}
}
}
return true;
}
};function isBipartite(graph) {
const n = graph.length;
const color = new Array(n).fill(-1);
for (let s = 0; s < n; s++) {
if (color[s] !== -1) continue;
const q = [s];
let head = 0;
color[s] = 0;
while (head < q.length) {
const u = q[head++];
for (const v of graph[u]) {
if (color[v] === -1) { color[v] = 1 - color[u]; q.push(v); }
else if (color[v] === color[u]) return false;
}
}
}
return true;
}2DFS two-colouring
O(V + E)O(V)Same idea recursively: colour a node, then try to colour each neighbour with the opposite colour.
- dfs(u, c): color[u] = c; for each v: if uncoloured and !dfs(v, 1 - c) return false; if same colour return false.
class Solution {
public boolean isBipartite(int[][] graph) {
int[] color = new int[graph.length];
Arrays.fill(color, -1);
for (int s = 0; s < graph.length; s++)
if (color[s] == -1 && !dfs(graph, s, 0, color)) return false;
return true;
}
private boolean dfs(int[][] g, int u, int c, int[] color) {
color[u] = c;
for (int v : g[u]) {
if (color[v] == -1) { if (!dfs(g, v, 1 - c, color)) return false; }
else if (color[v] == c) return false;
}
return true;
}
}class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
color = [-1] * len(graph)
for s in range(len(graph)):
if color[s] == -1 and not self.dfs(graph, s, 0, color):
return False
return True
def dfs(self, g: List[List[int]], u: int, c: int, color: List[int]) -> bool:
color[u] = c
for v in g[u]:
if color[v] == -1:
if not self.dfs(g, v, 1 - c, color):
return False
elif color[v] == c:
return False
return Trueclass Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
vector<int> color(graph.size(), -1);
for (int s = 0; s < (int)graph.size(); s++)
if (color[s] == -1 && !dfs(graph, s, 0, color)) return false;
return true;
}
private:
bool dfs(vector<vector<int>>& g, int u, int c, vector<int>& color) {
color[u] = c;
for (int v : g[u]) {
if (color[v] == -1) { if (!dfs(g, v, 1 - c, color)) return false; }
else if (color[v] == c) return false;
}
return true;
}
};function isBipartite(graph) {
const color = new Array(graph.length).fill(-1);
for (let s = 0; s < graph.length; s++)
if (color[s] === -1 && !dfs(graph, s, 0, color)) return false;
return true;
}
function dfs(g, u, c, color) {
color[u] = c;
for (const v of g[u]) {
if (color[v] === -1) { if (!dfs(g, v, 1 - c, color)) return false; }
else if (color[v] === c) return false;
}
return true;
}Edge cases to test
- Disconnected graph
- Isolated nodes
Hints
Hint 1
Try to colour the graph with two colours so every edge joins different colours. It fails exactly when there is an odd cycle.
FAQ
What is the best time complexity for Is Graph Bipartite??
DFS two-colouring runs in O(V + E) time and O(V) extra space.
Which pattern does Is Graph Bipartite? use?
It is a graphs problem that uses the cycle detection pattern. Other problems with the same pattern: Undirected Graph Cycle, Directed Graph Cycle, Detect Cycles in 2D Grid.
Is there a brute force solution for Is Graph Bipartite??
Yes. BFS two-colouring takes O(V + E) time and O(V) space. Colour an uncoloured node 0, then give every neighbour the opposite colour with BFS.
Which edge cases should I test for Is Graph Bipartite??
Disconnected graph; Isolated nodes.