Log inSign up
mediumLeetCodeNot Started

Bipartite Graph

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

### Problem Statement

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v.

The graph has the following properties: - There are no self-edges (graph[u] does not contain u). - There are no parallel edges (graph[u] does not contain duplicate values). - If v is in graph[u], then u is in graph[v] (the graph is undirected). - The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true *if and only if it is bipartite*.

---

### Examples

Example 1: ``text Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]] Output: false Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other. Specifically, nodes 0, 1, and 2 form an odd cycle of length 3 (a triangle), so they cannot be 2-colored.

Example 2: ``text Input: graph = [[1,3],[0,2],[1,3],[0,2]] Output: true Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}. All edges connect a node in {0, 2} to a node in {1, 3}.

---

### Constraints - graph.length == n - 1 <= n <= 100 - 0 <= graph[u].length < n - 0 <= graph[u][i] <= n - 1 - graph[u] does not contain u. - All the values of graph[u] are unique. - If graph[u] contains v, then graph[v] contains u.

Constraints:

  • graph.length == n
  • 1 <= n <= 100
  • 0 <= graph[u].length < n
  • 0 <= graph[u][i] <= n - 1
  • No self-edges or duplicate edges
  • Graph may be disconnected

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 2-coloring algorithm using BFS and DFS.
  • Understand the mathematical equivalence between bipartite graphs and absence of odd cycles.
  • Properly handle disconnected components in graph validation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Partitioning nodes into two independent sets with no intra-set edges
  • Graph 2-coloring problem
  • Checking for odd cycles in an undirected graph

Algorithmic Decision Tree:

  • If 2-colorable without edge conflicts -> Bipartite (return true).
  • If any neighbor has the same color -> Odd cycle detected, return false immediately.
  • Always iterate all vertices 0 to n-1 to handle disconnected subgraphs.

Connected Patterns:

Possible BipartitionGraph Coloring ProblemShortest Cycle in a Graph

1. Iterative BFS 2-Coloring

Intuition

Initialize all node colors to -1. For each uncolored node i, color it 0, push to queue, and expand. If an uncolored neighbor is found, assign color 1 - currColor and enqueue. If an already-colored neighbor has the same color, return false.

Algorithm

  1. Initialize color array of size n to -1.
  2. Loop i from 0 to n - 1:
  3. If color[i] == -1:
  4. color[i] = 0.
  5. Initialize queue q and push i.
  6. While queue is not empty:
  7. Pop u from q.
  8. For each neighbor v in graph[u]:
  9. If color[v] == -1:
  10. color[v] = 1 - color[u].
  11. Push v into q.
  12. Else if color[v] == color[u]:
  13. Return false (odd cycle detected).
  14. Return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 bool isBipartite(std::vector<std::vector<int>>& graph) {
8 int n = graph.size();
9 std::vector<int> color(n, -1);
10
11 for (int i = 0; i < n; ++i) {
12 if (color[i] == -1) {
13 color[i] = 0;
14 std::queue<int> q;
15 q.push(i);
16
17 while (!q.empty()) {
18 int u = q.front();
19 q.pop();
20
21 for (int v : graph[u]) {
22 if (color[v] == -1) {
23 color[v] = 1 - color[u];
24 q.push(v);
25 } else if (color[v] == color[u]) {
26 return false; // Odd cycle detected
27 }
28 }
29 }
30 }
31 }
32 return true;
33 }
34};
35
36int main() {
37 Solution sol;
38 std::vector<std::vector<int>> g1 = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
39 std::vector<std::vector<int>> g2 = {{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
40
41 std::cout << "Graph 1 Bipartite: " << (sol.isBipartite(g1) ? "true" : "false") << " (Expected: true)\n";
42 std::cout << "Graph 2 Bipartite: " << (sol.isBipartite(g2) ? "true" : "false") << " (Expected: false)\n";
43 return 0;
44}

Time & Space Complexity

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

2. Disjoint Set Union (DSU / Union-Find)

Intuition

In a bipartite graph, all neighbors of node u must reside in the opposite partition. Therefore, all neighbors of u can be unioned with each other. If u is ever in the same disjoint set as one of its neighbors, an odd cycle exists.

Algorithm

  1. Initialize DSU of size n.
  2. Loop u from 0 to n - 1:
  3. For each neighbor v in graph[u]:
  4. If find(u) == find(v): return false (same partition conflict).
  5. Union v with graph[u][0] (all neighbors belong to same group).
  6. Return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class DSU {
5 std::vector<int> parent, rank;
6public:
7 DSU(int n) : parent(n), rank(n, 0) {
8 for (int i = 0; i < n; ++i) parent[i] = i;
9 }
10 int find(int i) {
11 if (parent[i] == i) return i;
12 return parent[i] = find(parent[i]);
13 }
14 void unite(int i, int j) {
15 int rootI = find(i);
16 int rootJ = find(j);
17 if (rootI != rootJ) {
18 if (rank[rootI] < rank[rootJ]) std::swap(rootI, rootJ);
19 parent[rootJ] = rootI;
20 if (rank[rootI] == rank[rootJ]) rank[rootI]++;
21 }
22 }
23};
24
25class Solution {
26public:
27 bool isBipartite(std::vector<std::vector<int>>& graph) {
28 int n = graph.size();
29 DSU dsu(n);
30
31 for (int u = 0; u < n; ++u) {
32 for (int v : graph[u]) {
33 if (dsu.find(u) == dsu.find(v)) {
34 return false;
35 }
36 dsu.unite(graph[u][0], v);
37 }
38 }
39 return true;
40 }
41};
42
43int main() {
44 Solution sol;
45 std::vector<std::vector<int>> g1 = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
46 std::vector<std::vector<int>> g2 = {{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
47 std::cout << "DSU Graph 1: " << (sol.isBipartite(g1) ? "true" : "false") << "\n";
48 std::cout << "DSU Graph 2: " << (sol.isBipartite(g2) ? "true" : "false") << "\n";
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O(V + E * alpha(V))
  • Space complexity: O(V)

3. Canonical Recursive DFS 2-Coloring (Industry Benchmark)

Intuition

The cleanest and most standard interview approach. A boolean helper dfs(node, c) colors the current node with c and verifies all neighbors can be colored with 1 - c. If any neighbor already possesses color c, an odd cycle is confirmed.

Algorithm

  1. Initialize color array of size n to -1.
  2. Define dfs(u, c):
  3. color[u] = c.
  4. For each neighbor v in graph[u]:
  5. If color[v] == -1:
  6. If !dfs(v, 1 - c): return false.
  7. Else if color[v] == c:
  8. Return false (conflict).
  9. Return true.
  10. Loop i from 0 to n - 1:
  11. If color[i] == -1:
  12. If !dfs(i, 0): return false.
  13. Return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 bool dfs(int u, int c, const std::vector<std::vector<int>>& graph, std::vector<int>& color) {
6 color[u] = c;
7
8 for (int v : graph[u]) {
9 if (color[v] == -1) {
10 if (!dfs(v, 1 - c, graph, color)) return false;
11 } else if (color[v] == c) {
12 return false; // Same color on both endpoints
13 }
14 }
15 return true;
16 }
17public:
18 bool isBipartite(std::vector<std::vector<int>>& graph) {
19 int n = graph.size();
20 std::vector<int> color(n, -1);
21
22 for (int i = 0; i < n; ++i) {
23 if (color[i] == -1) {
24 if (!dfs(i, 0, graph, color)) return false;
25 }
26 }
27 return true;
28 }
29};
30
31int main() {
32 Solution sol;
33 std::vector<std::vector<int>> g1 = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
34 std::vector<std::vector<int>> g2 = {{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
35
36 std::cout << "Canonical DFS Graph 1: " << (sol.isBipartite(g1) ? "true" : "false") << " (Expected: true)\n";
37 std::cout << "Canonical DFS Graph 2: " << (sol.isBipartite(g2) ? "true" : "false") << " (Expected: false)\n";
38 return 0;
39}

Time & Space Complexity

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

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Iterative BFS 2-ColoringO(V + E)O(V)FIFO queue explores layer by layer, assigning alternating colors.Queue memory footprint
2.Disjoint Set Union (DSU)O(V + E * alpha(V))O(V)Unions all neighbors of a node together and checks partition parity.Find and union operations
3.Canonical Recursive DFS 2-ColoringOptimalO(V + E)O(V)Recursive helper alternates color 1 - c and returns false on conflict.Call stack depth

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Assuming the graph is connected and only running traversal starting from node 0.

Pitfall 2:

Not initializing the color array to an unvisited sentinel like -1.

Pitfall 3:

Flipping colors using bitwise NOT without masking (e.g. ~c gives -1 instead of 0 or 1; use 1 - c or c ^ 1).

Crucial Edge Cases to Validate:

  • Disconnected graph with multiple components — Outer loop checks every uncolored vertex, ensuring every component is 2-colored.
  • Graph with no edges (graph = [[], [], []]) — Every node is an isolated island, 2-coloring succeeds trivially, returns true.
  • Odd cycle of length 3 (triangle 0-1-2-0) — When visiting edge from 2 back to 0, both 2 and 0 share color 0, immediately returns false.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State König's Theorem upfront: 'A graph is bipartite if and only if it contains no odd cycles.'
  2. Highlight the outer loop for disconnected components immediately.
  3. Show how 1 - c cleanly toggles between 0 and 1.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Which graph theoretical property is necessary and sufficient for an undirected graph to be bipartite?

2.Why must the 2-coloring traversal be invoked inside an outer loop for (int i = 0; i < n; ++i)?

3.What does color[v] == color[u] indicate during traversal?

Back to DSA Sheet