Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Is Graph Bipartite?

MEDIUMProblemSolveExternal Links

Description

You are given an undirected graph containing n nodes, numbered from 0 to n - 1. The graph is provided as a 2D array called graph, where graph[u] lists all the nodes that are directly connected to node u by an edge.

The graph has these properties:

  • There are no self-edges (a node is never connected to itself).
  • There are no parallel edges (no duplicate connections between the same pair of nodes).
  • The graph is undirected: if node v appears in graph[u], then node u also appears in graph[v].
  • The graph may not be connected, meaning some nodes might have no path between them.

A graph is called bipartite if you can split all the nodes into two independent groups (call them Set A and Set B) such that every edge in the graph connects a node from Set A to a node from Set B. In other words, no two nodes within the same group are connected by an edge.

Return true if the graph is bipartite, and false otherwise.

Diagram showing a bipartite graph with nodes split into two groups where edges only cross between groups, and a non-bipartite graph with an odd cycle
Diagram showing a bipartite graph with nodes split into two groups where edges only cross between groups, and a non-bipartite graph with an odd cycle

Examples

Example 1

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

Output: false

Explanation: The graph has 4 nodes with the following connections:

  • Node 0 connects to 1, 2, and 3
  • Node 1 connects to 0 and 2
  • Node 2 connects to 0, 1, and 3
  • Node 3 connects to 0 and 2

Nodes 0, 1, and 2 form a triangle (each pair is connected). A triangle is an odd-length cycle (length 3). No matter how you try to split these three nodes into two groups, at least one edge will have both endpoints in the same group. For instance, if you put 0 in Set A, then 1 and 2 must both go to Set B — but 1 and 2 are also connected to each other, violating the bipartite condition.

Example 2

Input: graph = [[1,3],[0,2],[1,3],[0,2]]

Output: true

Explanation: The graph has 4 nodes forming a square cycle: 0–1–2–3–0.

  • Node 0 connects to 1 and 3
  • Node 1 connects to 0 and 2
  • Node 2 connects to 1 and 3
  • Node 3 connects to 0 and 2

We can partition the nodes into Set A = {0, 2} and Set B = {1, 3}. Every edge connects a node in Set A to a node in Set B:

  • Edge (0,1): A→B ✓
  • Edge (0,3): A→B ✓
  • Edge (1,2): B→A ✓
  • Edge (2,3): A→B ✓

Since all edges cross between sets, the graph is bipartite.

Example 3

Input: graph = [[]]

Output: true

Explanation: A single node with no edges is trivially bipartite. With no edges to violate the condition, you can place the single node in either set.

Constraints

  • graph.length == n
  • 1 ≤ n ≤ 100
  • 0 ≤ graph[u].length < n
  • 0 ≤ graph[u][i] ≤ n - 1
  • graph[u] does not contain u (no self-edges)
  • All values of graph[u] are unique (no parallel edges)
  • If graph[u] contains v, then graph[v] contains u (undirected graph)

Editorial

Brute Force

Intuition

The most straightforward way to check if a graph is bipartite is to directly test the definition: try every possible way to divide the nodes into two groups, and for each division, verify whether all edges cross between the two groups.

Imagine you have a classroom of students, and some pairs of students are friends (edges). You want to split the class into two teams for a debate, with the rule that no two friends can be on the same team. The brute force approach is to try every possible team assignment — put each student on Team A or Team B in every possible combination — and check if any assignment satisfies the rule.

With n nodes, each node can go into one of two groups, giving us 2^n total possible partitions. For each partition, we scan every edge to check if both endpoints land in the same group. If we find even one valid partition, the graph is bipartite. If no partition works, it is not.

Step-by-Step Explanation

Let's trace through with graph = [[1,2,3],[0,2],[0,1,3],[0,2]] (4 nodes, edges: (0,1), (0,2), (0,3), (1,2), (2,3)):

Step 1: There are 2^4 = 16 possible ways to assign 4 nodes to two groups (Set A = color 0, Set B = color 1). We systematically try each one.

Step 2: Attempt 1 — Assign {0→A, 1→A, 2→B, 3→B}. Check edge (0,1): both nodes 0 and 1 are in Set A. Conflict! This partition is invalid.

Step 3: Attempt 2 — Assign {0→A, 1→B, 2→A, 3→B}. Check edge (0,1): A→B ✓. Check edge (0,2): both in A. Conflict! Invalid.

Step 4: Attempt 3 — Assign {0→A, 1→B, 2→B, 3→A}. Check edge (0,1): A→B ✓. Check edge (0,3): both in A. Conflict! Invalid.

Step 5: Attempt 4 — Assign {0→A, 1→B, 2→B, 3→B}. Since node 0 connects to 1, 2, and 3 and all of those are in B, those edges are fine. But check edge (1,2): both in B. Conflict! The triangle 0-1-2 ensures that placing 1 and 2 in the same group always fails.

Step 6: After exhausting all 16 partitions, every single one has at least one edge where both endpoints share a group. The odd-length triangle (0-1-2) makes valid 2-coloring impossible. Return false.

Brute Force — Trying All 2-Partitions — Watch as we attempt different ways to split nodes into two groups. Each attempt fails because the triangle 0-1-2 always forces a conflict.

Algorithm

  1. For every possible assignment of n nodes into two groups (2^n total assignments):
    a. Assign each node to either Group A (color 0) or Group B (color 1)
    b. For every edge (u, v) in the graph:
    • If both u and v are in the same group, mark this assignment as invalid and break
      c. If all edges cross between groups, return true (graph is bipartite)
  2. If no valid assignment was found after checking all 2^n possibilities, return false

Code

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n);
        return tryAllColorings(graph, color, 0);
    }

private:
    bool tryAllColorings(vector<vector<int>>& graph,
                         vector<int>& color, int idx) {
        if (idx == (int)color.size()) {
            // All nodes assigned — verify every edge
            for (int u = 0; u < (int)color.size(); u++) {
                for (int v : graph[u]) {
                    if (color[u] == color[v])
                        return false;
                }
            }
            return true;
        }
        // Try assigning color 0 (Set A) to this node
        color[idx] = 0;
        if (tryAllColorings(graph, color, idx + 1))
            return true;
        // Try assigning color 1 (Set B) to this node
        color[idx] = 1;
        if (tryAllColorings(graph, color, idx + 1))
            return true;
        return false;
    }
};
class Solution:
    def isBipartite(self, graph: list[list[int]]) -> bool:
        n = len(graph)
        color = [0] * n

        def is_valid():
            for u in range(n):
                for v in graph[u]:
                    if color[u] == color[v]:
                        return False
            return True

        def try_all(idx):
            if idx == n:
                return is_valid()
            # Try assigning color 0 (Set A)
            color[idx] = 0
            if try_all(idx + 1):
                return True
            # Try assigning color 1 (Set B)
            color[idx] = 1
            if try_all(idx + 1):
                return True
            return False

        return try_all(0)
class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        return tryAllColorings(graph, color, 0);
    }

    private boolean tryAllColorings(int[][] graph,
                                     int[] color, int idx) {
        if (idx == color.length) {
            // All nodes assigned — verify every edge
            for (int u = 0; u < color.length; u++) {
                for (int v : graph[u]) {
                    if (color[u] == color[v])
                        return false;
                }
            }
            return true;
        }
        // Try assigning color 0 (Set A)
        color[idx] = 0;
        if (tryAllColorings(graph, color, idx + 1))
            return true;
        // Try assigning color 1 (Set B)
        color[idx] = 1;
        if (tryAllColorings(graph, color, idx + 1))
            return true;
        return false;
    }
}

Complexity Analysis

Time Complexity: O(2^n × E)

We generate all 2^n possible 2-colorings of the n nodes. For each coloring, we verify every edge in the graph, which takes O(E) time where E is the number of edges. In the worst case (no valid partition exists), we check all 2^n colorings before concluding the graph is not bipartite.

For the given constraint n ≤ 100, 2^100 ≈ 1.27 × 10^30. Even for modest values like n = 30, 2^30 ≈ 10^9 iterations would already exceed typical time limits.

Space Complexity: O(n)

We use a color array of size n and the recursion stack can go up to depth n. No additional data structures that grow beyond O(n) are needed.

Why This Approach Is Not Efficient

The brute force approach has an exponential time complexity of O(2^n × E). With n up to 100, the number of partitions is 2^100 ≈ 1.27 × 10^30 — an astronomically large number that no computer can iterate through in any reasonable time.

The fundamental flaw is that we treat the problem as a global search over all possible assignments, ignoring the local structure of the graph. We do not leverage the fact that the coloring decision for one node directly constrains its neighbors.

Key insight: Instead of guessing all possible 2-colorings and checking afterward, we can propagate constraints through the graph. If we color node 0 as Red, then all neighbors of node 0 must be Blue, and all neighbors of those Blue nodes must be Red, and so on. This cascading logic means we only need to visit each node and edge once — a single traversal of the graph using BFS or DFS can determine bipartiteness in O(V + E) time.

This transforms the problem from an exponential global search into a linear local propagation.

Optimal Approach - BFS 2-Coloring

Intuition

Instead of trying every possible partition, we can determine bipartiteness with a single graph traversal by exploiting constraint propagation.

Think of it like this: imagine each node is a person at a party, and you want to split everyone into two rooms — Room Red and Room Blue — such that no two friends (connected by an edge) end up in the same room. Instead of trying every possible arrangement, you start with one person, put them in Room Red, then tell all their friends: 'You must go to Room Blue.' Then you tell all friends of those Blue people: 'You must go to Room Red.' You keep propagating this rule through the social network.

If at any point you encounter someone who has already been placed in a room, and they are in the wrong room (the same room as the person sending them), then the split is impossible. If you successfully process everyone without conflicts, the split works.

This is exactly what BFS (Breadth-First Search) does. We start from an uncolored node, assign it color 0, put it in a queue, and process nodes level by level. Each uncolored neighbor gets the opposite color of the current node. If a neighbor is already colored and has the same color as the current node, we have found an odd-length cycle, and the graph is not bipartite.

Since the graph may be disconnected, we repeat this BFS from every uncolored node to ensure all connected components are checked.

Step-by-Step Explanation

Let's trace through with graph = [[1,2,3],[0,2],[0,1,3],[0,2]] (not bipartite):

Step 1: Initialize a color array: color = [-1, -1, -1, -1]. All nodes are uncolored.

Step 2: Node 0 is uncolored. Start BFS from node 0. Assign color 0 (Red). Queue = [0].

Step 3: Dequeue node 0 (color 0). Its neighbors are [1, 2, 3].

Step 4: Neighbor 1 is uncolored → assign color 1 (Blue). Enqueue. Queue = [1].

Step 5: Neighbor 2 is uncolored → assign color 1 (Blue). Enqueue. Queue = [1, 2].

Step 6: Neighbor 3 is uncolored → assign color 1 (Blue). Enqueue. Queue = [1, 2, 3]. All of node 0's neighbors are now colored.

Step 7: Dequeue node 1 (color 1/Blue). Its neighbors are [0, 2].

Step 8: Check neighbor 0: color[0] = 0 (Red), color[1] = 1 (Blue). Different colors — no conflict ✓.

Step 9: Check neighbor 2: color[2] = 1 (Blue), color[1] = 1 (Blue). SAME COLOR! Both are Blue but connected by an edge. CONFLICT DETECTED!

Step 10: Return false. The BFS coloring forced nodes 1 and 2 into the same color (both must be opposite to node 0), yet nodes 1 and 2 are also adjacent. This unsolvable conflict proves the graph is not bipartite.

BFS 2-Coloring — Detecting Non-Bipartite Graph — Watch how BFS propagates colors level by level. When a neighbor already has the same color as the current node, a conflict proves the graph is not bipartite.

Algorithm

  1. Create a color array of size n, initialized to -1 (uncolored)
  2. For each node i from 0 to n-1:
    • If node i is already colored, skip it
    • Otherwise, start BFS from node i:
      a. Assign color 0 to node i and add it to a queue
      b. While the queue is not empty:
      • Dequeue a node u
      • For each neighbor v of u:
        • If v is uncolored: assign color 1 - color[u] (opposite color) and enqueue v
        • If v is already colored and color[v] == color[u]: return false (conflict found)
  3. If all nodes are processed without conflict, return true

Code

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, -1);

        for (int i = 0; i < n; i++) {
            if (color[i] != -1) continue;

            // Start BFS from uncolored node i
            queue<int> q;
            q.push(i);
            color[i] = 0;

            while (!q.empty()) {
                int node = q.front();
                q.pop();

                for (int neighbor : graph[node]) {
                    if (color[neighbor] == -1) {
                        // Uncolored — assign opposite color
                        color[neighbor] = 1 - color[node];
                        q.push(neighbor);
                    } else if (color[neighbor] == color[node]) {
                        // Same color — conflict detected
                        return false;
                    }
                }
            }
        }
        return true;
    }
};
from collections import deque

class Solution:
    def isBipartite(self, graph: list[list[int]]) -> bool:
        n = len(graph)
        color = [-1] * n

        for i in range(n):
            if color[i] != -1:
                continue

            # Start BFS from uncolored node i
            queue = deque([i])
            color[i] = 0

            while queue:
                node = queue.popleft()

                for neighbor in graph[node]:
                    if color[neighbor] == -1:
                        # Uncolored — assign opposite color
                        color[neighbor] = 1 - color[node]
                        queue.append(neighbor)
                    elif color[neighbor] == color[node]:
                        # Same color — conflict detected
                        return False

        return True
import java.util.*;

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        Arrays.fill(color, -1);

        for (int i = 0; i < n; i++) {
            if (color[i] != -1) continue;

            // Start BFS from uncolored node i
            Queue<Integer> queue = new LinkedList<>();
            queue.add(i);
            color[i] = 0;

            while (!queue.isEmpty()) {
                int node = queue.poll();

                for (int neighbor : graph[node]) {
                    if (color[neighbor] == -1) {
                        // Uncolored — assign opposite color
                        color[neighbor] = 1 - color[node];
                        queue.add(neighbor);
                    } else if (color[neighbor] == color[node]) {
                        // Same color — conflict detected
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(V + E)

Where V is the number of vertices (nodes) and E is the number of edges. The BFS traversal visits each vertex exactly once (we skip nodes that are already colored). For each vertex, we iterate through its adjacency list, examining each edge. Since every edge is represented twice in an undirected graph's adjacency list, the total work across all adjacency lists is O(2E) = O(E). Combined with the O(V) outer loop, the total time is O(V + E).

For the given constraints (n ≤ 100), this runs in at most a few hundred operations — virtually instant.

Space Complexity: O(V)

We use a color array of size V to store the color assignment of each node. The BFS queue can hold at most V nodes in the worst case (when all nodes are in a single connected component and added to the queue before any is processed). No additional data structures that scale with input size are required.