Problem Description

You are given an undirected graph with n nodes numbered from 0 to n - 1. The graph is represented as a 2D array graph, where graph[u] contains all nodes that are adjacent to node u.

The graph has these properties:

• No self-edges (a node doesn't connect to itself)
• No parallel edges (no duplicate connections between the same pair of nodes)
• Undirected edges (if node v is in graph[u], then node u is in graph[v])
• May not be connected (some nodes might not have a path between them)

A graph is bipartite if you can split all nodes into two independent sets A and B such that every edge connects a node from set A to a node from set B. In other words, no two nodes within the same set are connected.

Your task is to determine if the given graph is bipartite. Return true if it is bipartite, otherwise return false.

The solution uses a coloring approach with DFS. The idea is to try coloring the graph using two colors (represented as 1 and -1). Starting from each uncolored node, we assign it one color and recursively assign the opposite color to all its neighbors. If at any point we find a neighbor that has already been colored with the same color as the current node, the graph cannot be bipartite. The color array tracks the color of each node, where 0 means uncolored, 1 represents one color, and -1 represents the other color.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem explicitly states we have an undirected graph with n nodes, where graph[u] contains all adjacent nodes to node u.

Is it a tree?

• No: The graph may have cycles (not mentioned to be acyclic) and may not even be connected. Trees must be connected and acyclic.

Is the problem related to directed acyclic graphs?

• No: The graph is undirected, not directed.

Is the problem related to shortest paths?

• No: We're not finding shortest paths between nodes. We're determining if the graph can be colored with two colors (bipartite property).

Does the problem involve connectivity?

• No: While the graph may not be connected, we're not specifically solving connectivity problems like finding connected components or checking if nodes are connected.

Does the problem have small constraints?

• Yes: Although not explicitly stated in this problem description, graph coloring problems often have manageable constraints that allow for DFS exploration.

DFS/backtracking?

• Yes: DFS is perfect for this problem as we need to traverse the graph and color nodes, checking if we can maintain the bipartite property (alternating colors).

Conclusion: The flowchart suggests using a DFS approach. This aligns perfectly with the solution, which uses DFS to traverse the graph and attempt to color it with two colors. Starting from each uncolored node, we assign it a color and recursively color all its neighbors with the opposite color. If we encounter a conflict (a neighbor already has the same color), the graph is not bipartite.

Intuition

The key insight for determining if a graph is bipartite comes from understanding what a bipartite graph fundamentally represents: a graph where nodes can be divided into two groups such that all edges connect nodes from different groups.

Think of it like organizing a party where some guests don't get along. You want to split them into two rooms such that people who don't get along (connected by an edge) are in different rooms. If you can successfully do this, the graph is bipartite.

This naturally leads to a coloring problem. Imagine painting nodes with two colors - let's say red and blue. If we can color the entire graph such that no two adjacent nodes have the same color, then we've successfully partitioned the nodes into two independent sets (red nodes and blue nodes).

The process works like this:

1. Start with any uncolored node and paint it red (color = 1)
2. All its neighbors must be blue (color = -1)
3. All neighbors of those blue nodes must be red
4. Continue this alternating pattern

If at any point we try to paint a node and find that it's already painted with the wrong color, we've discovered a conflict - the graph cannot be bipartite. This happens when we encounter an odd-length cycle in the graph.

Why DFS? Because we need to propagate the coloring constraint through connected components. When we color a node, we immediately need to color all its neighbors with the opposite color, and then their neighbors, and so on. DFS naturally follows this propagation pattern.

The reason we loop through all nodes in the main function is that the graph might not be connected. We need to check each disconnected component separately - if any component is not bipartite, the entire graph is not bipartite.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.

Solution Approach

The solution implements the coloring method to determine if a graph is bipartite using Depth-First Search (DFS).

Data Structure:

• color array: Tracks the color of each node where:
  • 0 means uncolored (not visited yet)
  • 1 represents one color (e.g., red)
  • -1 represents the opposite color (e.g., blue)

Implementation Details:

1. DFS Helper Function dfs(a, c):

   • Takes node a and color c as parameters
   • Colors node a with color c: color[a] = c
   • Iterates through all neighbors b of node a
   • For each neighbor, checks two conditions:
     • If color[b] == c: The neighbor already has the same color as the current node - conflict detected, return False
     • If color[b] == 0: The neighbor is uncolored, so recursively color it with the opposite color dfs(b, -c). If this recursive call returns False, propagate the failure
   • If all neighbors are successfully processed, return True

2. Main Logic:

   • Initialize the color array with zeros for all n nodes
   • Iterate through each node i from 0 to n-1
   • For each uncolored node (color[i] == 0):
     • Start DFS coloring from this node with color 1
     • If DFS returns False, the graph is not bipartite, return False
   • If all components are successfully colored, return True

Why This Works:

The algorithm exploits the property that in a bipartite graph, nodes can be colored with two colors such that no adjacent nodes share the same color. The DFS ensures that once we color a node, all nodes in its connected component get colored consistently.

The clever use of -c to alternate colors ensures that adjacent nodes always get opposite colors. Starting with color 1, neighbors get -1, their neighbors get -(-1) = 1, and so on, creating the alternating pattern needed for bipartite graphs.

The outer loop handles disconnected components - each component is checked independently, and the graph is bipartite only if all components are bipartite.

Example Walkthrough

Let me walk through a small example to illustrate the solution approach.

Example Graph:

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

This represents:

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

Visual representation:

0 --- 1
|     |
|     |
3 --- 2

Step-by-step execution:

1. Initialize: color = [0, 0, 0, 0] (all nodes uncolored)

2. Process node 0:

   • color[0] == 0, so start DFS from node 0 with color 1
   • DFS(0, 1):
     • Color node 0: color = [1, 0, 0, 0]
     • Check neighbor 1: uncolored, so call DFS(1, -1)

3. DFS(1, -1):

   • Color node 1: color = [1, -1, 0, 0]
   • Check neighbor 0: already colored with 1 (different from -1), OK
   • Check neighbor 2: uncolored, so call DFS(2, 1)

4. DFS(2, 1):

   • Color node 2: color = [1, -1, 1, 0]
   • Check neighbor 1: already colored with -1 (different from 1), OK
   • Check neighbor 3: uncolored, so call DFS(3, -1)

5. DFS(3, -1):

   • Color node 3: color = [1, -1, 1, -1]
   • Check neighbor 0: already colored with 1 (different from -1), OK
   • Check neighbor 2: already colored with 1 (different from -1), OK
   • Return True

6. Back to main loop:

   • Node 1: already colored, skip
   • Node 2: already colored, skip
   • Node 3: already colored, skip
   • All nodes processed successfully, return True

Final coloring: color = [1, -1, 1, -1]

This means:

• Set A (color 1): nodes {0, 2}
• Set B (color -1): nodes {1, 3}

All edges connect nodes from different sets, confirming the graph is bipartite.

Counter-example (non-bipartite): If we had graph = [[1,2], [0,2], [0,1]] (a triangle), the algorithm would:

1. Color node 0 with 1
2. Color node 1 with -1 (neighbor of 0)
3. Color node 2 with -1 (neighbor of 0)
4. When processing node 1's neighbors, find node 2 already colored with -1 (same color)
5. Return False - conflict detected!

Solution Implementation

Time and Space Complexity

The time complexity is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. The DFS traversal visits each vertex once, taking O(V) time. For each vertex, we iterate through all its adjacent vertices (edges), which in total across all vertices takes O(E) time. Therefore, the overall time complexity is O(V + E).

Note that the reference answer states O(n) where n is the number of nodes. This is a simplified notation that assumes the graph is sparse (where E = O(V)), making the complexity O(V) or equivalently O(n).

The space complexity is O(V) or O(n), where n is the number of nodes. This accounts for:

• The color array which stores the color for each vertex: O(n)
• The recursive call stack in the worst case (for a path-like graph): O(n)

Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Disconnected Components

The Pitfall: A common mistake is assuming the graph is connected and only checking from node 0. This would miss disconnected components that might not be bipartite.

# WRONG: Only checks the component containing node 0
def isBipartite(self, graph: List[List[int]]) -> bool:
    colors = [0] * len(graph)
    return dfs(0, 1)  # Misses other components!

Why It's Wrong: If the graph has multiple disconnected components, nodes in other components would remain uncolored (color = 0) and never get checked. A non-bipartite component could be missed entirely.

The Solution: Always iterate through ALL nodes and start DFS from any uncolored node:

for node_idx in range(num_nodes):
    if colors[node_idx] == 0 and not dfs(node_idx, 1):
        return False

2. Incorrect Neighbor Color Check Logic

The Pitfall: Checking if a neighbor is already colored with the opposite color and trying to recolor it:

# WRONG: Attempting to recolor already colored nodes
def dfs(node, node_color):
    colors[node] = node_color
    for neighbor in graph[node]:
        if colors[neighbor] != 0 and colors[neighbor] != -node_color:
            return False
        if not dfs(neighbor, -node_color):  # This would recolor already colored nodes!
            return False
    return True

Why It's Wrong: This would attempt to revisit and recolor nodes that are already colored, leading to infinite recursion or incorrect results. Once a node is colored, it should not be recolored.

The Solution: Only recursively color uncolored neighbors:

for neighbor in graph[node]:
    if colors[neighbor] == node_color:  # Same color = conflict
        return False
    if colors[neighbor] == 0 and not dfs(neighbor, -node_color):  # Only color if uncolored
        return False

3. Using BFS Without Proper Queue Initialization

The Pitfall: When converting to BFS, forgetting to color the starting node before adding to queue:

# WRONG: Not coloring the start node before BFS
def isBipartite(self, graph: List[List[int]]) -> bool:
    colors = [0] * len(graph)
    for i in range(len(graph)):
        if colors[i] == 0:
            queue = deque([i])  # Added to queue but not colored!
            while queue:
                node = queue.popleft()
                for neighbor in graph[node]:
                    # Logic fails because node's color isn't set

The Solution: Always color the starting node before beginning BFS:

if colors[i] == 0:
    colors[i] = 1  # Color the starting node first
    queue = deque([i])