# 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

| Item | Meaning |
|---|---|
| Input | `graph`, an adjacency list |
| Output | `True` if the graph is bipartite, otherwise `False` |
| Nodes | Labeled from `0` to `n - 1` |
| Graph type | Undirected |
| Important detail | The graph may be disconnected |

Function shape:

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

## Examples

Example 1:

```python
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:

```python
False
```

Example 2:

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

One valid split is:

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

Every edge connects one node from each group.

The answer is:

```python
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:

```text
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:

| Situation | Meaning |
|---|---|
| Neighbor has no color | Assign the opposite color |
| Neighbor has opposite color | Good |
| Neighbor has same color | Not bipartite |

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

## Algorithm

Use an array `color`.

| Value | Meaning |
|---|---|
| `-1` | Node has no color yet |
| `0` | First color |
| `1` | Second 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.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n + e)` | Each node and edge is processed a constant number of times |
| Space | `O(n)` | The color array and recursion stack store up to `n` nodes |

## Implementation

```python
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:

```python
color = [-1] * n
```

Every node starts uncolored.

The DFS assigns the current node a color:

```python
color[node] = current_color
```

Then it checks every neighbor:

```python
for neighbor in graph[node]:
```

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

```python
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:

```python
elif color[neighbor] == current_color:
    return False
```

The outer loop handles disconnected graphs:

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

If no conflict appears, the graph is bipartite:

```python
return True
```

## BFS Version

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

```python
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

```python
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:

| Test | Why |
|---|---|
| Triangle conflict | Odd cycle cannot be bipartite |
| Four-node cycle | Valid bipartite graph |
| Single isolated node | No edges, always valid |
| Two connected nodes | Smallest non-trivial bipartite graph |
| Three-node complete triangle | Detects same-color conflict |
| Disconnected components | Checks outer loop over all nodes |