LeetCode 785: Is Graph Bipartite?

Problem Restatement

We are given an undirected graph as an adjacency list.

graph[i] contains all nodes connected to node i.

We need to return True if the graph is bipartite.

A graph is bipartite if its nodes can be split into two groups such that every edge connects nodes from different groups.

Equivalently, we need to check whether we can color every node using two colors so that no two adjacent nodes have the same color.

Input and Output

Function shape:

class Solution:
    def isBipartite(self, graph: list[list[int]]) -> bool:
        ...

Examples

Example 1:

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

This graph contains a triangle among nodes 0, 1, and 2.

If node 0 has color 0, then nodes 1 and 2 must both have color 1.

But nodes 1 and 2 are connected to each other, so they cannot have the same color.

The answer is:

False

Example 2:

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

One valid split is:

Group A: 0, 2
Group B: 1, 3

Every edge connects one node from each group.

The answer is:

True

First Thought: Try All Partitions

A direct way is to try assigning every node to one of two groups.

For each assignment, check every edge.

If every edge connects nodes from different groups, return True.

This is too slow.

For n nodes, there are:

2^n

possible assignments.

We need to use the graph structure instead.

Key Insight

A bipartite graph is the same as a graph that can be colored with two colors.

When we color a node, all of its neighbors are forced to have the opposite color.

So we can traverse the graph with DFS or BFS.

During traversal:

The graph may be disconnected, so we must start a traversal from every uncolored node.

Algorithm

Use an array color.

Then:

1. Initialize every node color to -1.
2. For each node:
   1. If it is already colored, skip it.
   2. Otherwise, start DFS from it and assign color 0.
3. During DFS:
   1. For every neighbor:
      1. If the neighbor has no color, assign the opposite color.
      2. If the neighbor has the same color, return False.
4. If every component is colored without conflict, return True.

Correctness

If the algorithm returns False, it found an edge connecting two nodes with the same color. In a bipartite graph, every edge must connect nodes from different groups. Therefore, such a graph cannot be bipartite.

If the algorithm returns True, then every visited edge connects nodes with opposite colors. Since the outer loop starts a traversal from every uncolored node, this applies to every connected component in the graph.

Let group A be all nodes colored 0, and group B be all nodes colored 1. Because every edge connects opposite colors, no edge has both endpoints inside A or both endpoints inside B.

So the graph can be partitioned into two independent sets, which means it is bipartite.

Therefore, the algorithm is correct.

Complexity

Let n be the number of nodes and e be the number of edges.

Implementation

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

        def dfs(node: int, current_color: int) -> bool:
            color[node] = current_color

            for neighbor in graph[node]:
                if color[neighbor] == -1:
                    if not dfs(neighbor, 1 - current_color):
                        return False
                elif color[neighbor] == current_color:
                    return False

            return True

        for node in range(n):
            if color[node] == -1:
                if not dfs(node, 0):
                    return False

        return True

Code Explanation

We create a color array:

color = [-1] * n

Every node starts uncolored.

The DFS assigns the current node a color:

color[node] = current_color

Then it checks every neighbor:

for neighbor in graph[node]:

If a neighbor has no color yet, it must receive the opposite color:

if color[neighbor] == -1:
    if not dfs(neighbor, 1 - current_color):
        return False

If a neighbor already has the same color, the graph violates the bipartite rule:

elif color[neighbor] == current_color:
    return False

The outer loop handles disconnected graphs:

for node in range(n):
    if color[node] == -1:
        if not dfs(node, 0):
            return False

If no conflict appears, the graph is bipartite:

return True

BFS Version

DFS and BFS are both valid. BFS avoids recursion depth concerns.

from collections import deque

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

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

            color[start] = 0
            queue = deque([start])

            while queue:
                node = queue.popleft()

                for neighbor in graph[node]:
                    if color[neighbor] == -1:
                        color[neighbor] = 1 - color[node]
                        queue.append(neighbor)
                    elif color[neighbor] == color[node]:
                        return False

        return True

Testing

def run_tests():
    s = Solution()

    assert s.isBipartite([[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]) is False
    assert s.isBipartite([[1, 3], [0, 2], [1, 3], [0, 2]]) is True

    assert s.isBipartite([[]]) is True
    assert s.isBipartite([[1], [0]]) is True
    assert s.isBipartite([[1, 2], [0, 2], [0, 1]]) is False

    assert s.isBipartite([[1], [0], [3], [2]]) is True

    print("all tests passed")

run_tests()

Test coverage: