# The Bipartite Test

> Can this crowd be split into two perfectly separated groups?

Canonical URL: <https://datadriven.io/problems/the_bipartite_test>

Domain: Python · Difficulty: medium · Seniority: L5

## Problem

Given a graph as an adjacency list (graph[i] is the list of neighbors of node i), return True if the graph is bipartite (2-colorable).

## Worked solution and explanation

### Why this problem exists in real interviews

Testing graph bipartiteness probes **BFS/DFS coloring** and whether you can detect odd-length cycles. It is a graph theory fundamental that appears in matching and scheduling problems.

---

### Break down the requirements

#### Step 1: Assign colors using BFS or DFS

Start at an unvisited node, assign it color 0. Assign the opposite color to all its neighbors.

#### Step 2: Detect conflicts

If a neighbor already has the same color as the current node, the graph is not bipartite.

#### Step 3: Handle disconnected components

Start a new BFS/DFS from any unvisited node until all nodes are colored.

---

### The solution

**BFS two-coloring across all connected components**

```python
from collections import deque
def is_bipartite(adj_list):
    n = len(adj_list)
    color = [-1] * n
    for start in range(n):
        if color[start] != -1:
            continue
        queue = deque([start])
        color[start] = 0
        while queue:
            node = queue.popleft()
            for neighbor in adj_list[node]:
                if color[neighbor] == -1:
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False
    return True
```

> **Time and Space Complexity**
>
> **Time:** O(V + E) where V is the number of nodes and E is the number of edges. Standard BFS complexity.
> 
> **Space:** O(V) for the color array and the BFS queue.

> **Interviewers Watch For**
>
> Handling disconnected components by looping over all unvisited start nodes. A single BFS from node 0 would miss disconnected subgraphs.

> **Common Pitfall**
>
> Only checking from node 0. If the graph has multiple connected components, some components might not be bipartite even if node 0's component is.

---

## Common follow-up questions

- What is the relationship between bipartiteness and odd cycles? _(Tests that a graph is bipartite if and only if it contains no odd-length cycles.)_
- How would you find the actual two-partition sets? _(Tests collecting nodes by their color assignment after a successful BFS.)_
- What if the graph is directed? _(Tests that bipartiteness is typically defined for undirected graphs; for directed graphs, you check the underlying undirected graph.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_bipartite_test)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.