LeetCode 785 - Is Graph Bipartite?

The problem asks whether a given undirected graph is bipartite. In simpler terms, we are given a graph represented as an adjacency list graph, where graph[u] lists all nodes directly connected to node u.

leetcodemediumdepth-first-searchbreadth-first-searchunion-findgraph-theory

LeetCode Problem 785

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

Solution

Problem Understanding

The problem asks whether a given undirected graph is bipartite. In simpler terms, we are given a graph represented as an adjacency list graph, where graph[u] lists all nodes directly connected to node u. The goal is to determine if it is possible to split all nodes into two sets such that no two nodes within the same set are connected by an edge.

The input graph has up to 100 nodes and may not be connected. Each node only lists distinct neighbors, there are no self-loops, and the graph is undirected, meaning if v is a neighbor of u, then u is also a neighbor of v. The expected output is a boolean: true if the graph is bipartite, false otherwise.

Important edge cases include graphs with disconnected components, graphs with cycles (especially odd-length cycles, which make bipartiteness impossible), and single-node graphs, which are trivially bipartite.

Approaches

A brute-force approach would attempt to enumerate all possible partitions of nodes into two sets and check whether each edge connects nodes from different sets. While this is theoretically correct, the approach is impractical because the number of partitions is exponential in the number of nodes, specifically 2^n, which is infeasible even for n = 20, let alone n = 100.

The optimal approach leverages a graph coloring technique. The key insight is that a graph is bipartite if and only if it is possible to color each node with one of two colors such that no two adjacent nodes share the same color. This property allows us to traverse the graph using either Depth-First Search (DFS) or Breadth-First Search (BFS), attempting to color nodes alternately. If we encounter a node that cannot be colored without violating the rule, the graph is not bipartite. This method works efficiently because we only visit each node and each edge once, giving a linear-time solution relative to the number of nodes and edges.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n^2) O(n) Check all partitions of nodes into two sets and validate edges
Graph Coloring (DFS/BFS) O(V + E) O(V) Use two-coloring to determine bipartiteness; traverses each node and edge once

Algorithm Walkthrough

  1. Initialize a dictionary or array color that stores the color of each node. Use two colors, typically 0 and 1. Initially, all nodes are uncolored.
  2. Iterate over all nodes in the graph. For each node that is uncolored, perform a DFS (or BFS) starting from that node to attempt to color the connected component.
  3. During DFS/BFS, color the current node with one color and assign the opposite color to all its neighbors.
  4. If a neighbor is already colored with the same color as the current node, return false immediately because the coloring rule is violated, indicating the graph is not bipartite.
  5. If all nodes are successfully colored without conflicts, return true.

Why it works: The two-coloring rule guarantees that nodes within the same set cannot be connected. By attempting to color the graph recursively or iteratively, any violation of bipartiteness will be detected as a coloring conflict. Since the algorithm checks all nodes, including disconnected components, it correctly handles graphs that are not connected.

Python Solution

from typing import List

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        color = {}

        def dfs(node: int, c: int) -> bool:
            if node in color:
                return color[node] == c
            color[node] = c
            for neighbor in graph[node]:
                if not dfs(neighbor, 1 - c):
                    return False
            return True

        for node in range(len(graph)):
            if node not in color:
                if not dfs(node, 0):
                    return False
        return True

Explanation: We use a dictionary color to store each node's assigned color. The dfs function attempts to color a node and recursively color its neighbors with the opposite color. If any neighbor already has the same color, we return false. The outer loop ensures that disconnected components are also checked.

Go Solution

func isBipartite(graph [][]int) bool {
    n := len(graph)
    color := make([]int, n)
    for i := range color {
        color[i] = -1
    }

    var dfs func(int, int) bool
    dfs = func(node int, c int) bool {
        if color[node] != -1 {
            return color[node] == c
        }
        color[node] = c
        for _, neighbor := range graph[node] {
            if !dfs(neighbor, 1 - c) {
                return false
            }
        }
        return true
    }

    for i := 0; i < n; i++ {
        if color[i] == -1 {
            if !dfs(i, 0) {
                return false
            }
        }
    }
    return true
}

Go-specific notes: We use a slice color initialized with -1 to represent uncolored nodes. Recursive DFS is implemented using a function variable. The logic is identical to the Python version.

Worked Examples

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

Node Neighbors Color Attempt Result
0 [1,2,3] 0 DFS proceeds
1 [0,2] 1 OK
2 [0,1,3] 1 Conflict: neighbor 1 already color 1

Result: false

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

Node Neighbors Color Attempt Result
0 [1,3] 0 DFS proceeds
1 [0,2] 1 OK
3 [0,2] 1 OK
2 [1,3] 0 OK

Result: true

Complexity Analysis

Measure Complexity Explanation
Time O(V + E) Each node and edge is visited at most once during DFS
Space O(V) Color map stores one entry per node; recursion stack can go up to V

The algorithm is linear in the size of the graph, which is efficient given the constraints.

Test Cases

# provided examples
assert Solution().isBipartite([[1,2,3],[0,2],[0,1,3],[0,2]]) == False  # odd cycle
assert Solution().isBipartite([[1,3],[0,2],[1,3],[0,2]]) == True  # even cycle

# boundary cases
assert Solution().isBipartite([[ ]]) == True  # single node
assert Solution().isBipartite([[1],[0]]) == True  # two connected nodes

# disconnected graph
assert Solution().isBipartite([[1],[0],[3],[2]]) == True

# graph with an odd-length cycle
assert Solution().isBipartite([[1,2],[0,2],[0,1]]) == False

# graph with multiple components, one non-bipartite
assert Solution().isBipartite([[1],[0],[3,4],[2,4],[2,3]]) == False
Test Why
[[1,2,3],[0,2],[0,1,3],[0,2]] Odd cycle prevents bipartition
[[1,3],[0,2],[1,3],[0,2]] Even cycle allows bipartition
[[]] Single node is trivially bipartite
[[1],[0]] Two connected nodes, bipartite
[[1],[0],[3],[2]] Disconnected components, each bipartite
[[1,2],[0,2],[0,1]] Odd-length cycle, non-bipartite
[[1],[0],[3,4],[2,4],[2,3]] Multi-component, one non-bipartite

Edge Cases

Disconnected graph: Some nodes may not be reachable from others. The algorithm handles this by iterating over all nodes and performing DFS on unvisited nodes, ensuring all components are checked.

Single-node graph: A graph with one node and no edges is trivially bipartite. The DFS correctly colors it without any conflicts.

Odd-length cycle: Any cycle of odd length cannot be bipartite. The DFS detects this when attempting to color a neighbor with the same color, immediately returning false. This ensures cycles are correctly handled.