# Is Graph Bipartite?
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/is-graph-bipartite)
Canonical: https://scaleengineer.com/dsa/problems/is-graph-bipartite
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Graph
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung), [Pinterest](https://scaleengineer.com/companies/pinterest)
---
## Problem
There is an **undirected** graph with `n` nodes, where each node is numbered between `0` and `n - 1`. You are given a 2D array `graph`, where `graph[u]` is an array of nodes that node `u` is adjacent to. More formally, for each `v` in `graph[u]`, there is an undirected edge between node `u` and node `v`. The graph has the following properties:

* There are no self-edges (`graph[u]` does not contain `u`).
* There are no parallel edges (`graph[u]` does not contain duplicate values).
* If `v` is in `graph[u]`, then `u` is in `graph[v]` (the graph is undirected).
* The graph may not be connected, meaning there may be two nodes `u` and `v` such that there is no path between them.

A graph is **bipartite** if the nodes can be partitioned into two independent sets `A` and `B` such that **every** edge in the graph connects a node in set `A` and a node in set `B`.

Return `true` _if and only if it is **bipartite**_.

**Example 1:**

![](https://assets.glich.co/dsa/is-graph-bipartite/image0.jpg) 

**Input:** graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
**Output:** false
**Explanation:** There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

**Example 2:**

![](https://assets.glich.co/dsa/is-graph-bipartite/image1.jpg) 

**Input:** graph = [[1,3],[0,2],[1,3],[0,2]]
**Output:** true
**Explanation:** We can partition the nodes into two sets: {0, 2} and {1, 3}.

**Constraints:**

* `graph.length == n`
* `1 <= n <= 100`
* `0 <= graph[u].length < n`
* `0 <= graph[u][i] <= n - 1`
* `graph[u]` does not contain `u`.
* All the values of `graph[u]` are **unique**.
* If `graph[u]` contains `v`, then `graph[v]` contains `u`.

# Approaches
## Depth-First Search (DFS) with Two-Coloring
This approach uses a recursive Depth-First Search (DFS) traversal to check for bipartiteness. The core idea is to assign one of two colors (e.g., 1 and -1) to each node. We start from an arbitrary uncolored node, assign it the first color, and then traverse its neighbors. Each neighbor is assigned the opposite color. If we encounter a neighbor that is already colored with the same color as the current node, we have found an odd-length cycle, which means the graph is not bipartite. Since the graph might be disconnected, we iterate through all nodes to ensure every component is checked.
**Time:** O(V + E), where V is the number of vertices and E is the number of edges. Each vertex is visited once, and each edge is checked once across all DFS calls. · **Space:** O(V), where V is the number of vertices. This space is used for the `colors` array and the recursion call stack. In the worst-case scenario of a path graph, the recursion depth can be up to V.
**Pros:** Conceptually straightforward and easy to implement using recursion.; Optimal time complexity for solving this problem.
**Cons:** The recursive implementation can lead to a `StackOverflowError` if the graph is very deep (i.e., has a very long path). However, given the constraint `n <= 100`, this is not a practical concern for this specific problem.
### Explanation
We use an auxiliary array, `colors`, to store the color of each node. A value of `0` means uncolored, `1` means color A, and `-1` means color B.
The main function iterates through all nodes. If a node hasn't been colored yet, we start a DFS from it with an initial color (e.g., 1).
The recursive DFS function `dfs(node, color)` works as follows:
1.  Color the current `node` with the given `color`.
2.  For each `neighbor` of the `node`:
    *   If the `neighbor` is uncolored, recursively call `dfs(neighbor, -color)`. If this recursive call returns `false`, it means a conflict was found deeper in the traversal, so we propagate `false` up.
    *   If the `neighbor` is already colored, check if `colors[neighbor] == colors[node]`. If they have the same color, it violates the bipartite property, so we return `false`.
3.  If the loop finishes without finding any conflicts, it means this part of the graph is bipartite, so we return `true`.
If the main loop completes and all components are successfully colored, the entire graph is bipartite.
```java
class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] colors = new int[n]; // 0: uncolored, 1: color A, -1: color B

        for (int i = 0; i < n; i++) {
            // If the node is not yet colored, start a DFS from it.
            if (colors[i] == 0) {
                if (!dfs(graph, colors, i, 1)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean dfs(int[][] graph, int[] colors, int node, int color) {
        colors[node] = color;
        for (int neighbor : graph[node]) {
            if (colors[neighbor] == 0) {
                // If neighbor is uncolored, color it with the opposite color and recurse.
                if (!dfs(graph, colors, neighbor, -color)) {
                    return false;
                }
            } else if (colors[neighbor] == color) {
                // If neighbor has the same color, conflict found.
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
*   Initialize a `colors` array of size `n` with `0`s (representing uncolored nodes).
*   Iterate through each node `i` from `0` to `n-1`.
*   If node `i` is uncolored (`colors[i] == 0`), it means we have found a new, unvisited component of the graph.
*   Start a recursive Depth-First Search (DFS) from this node. Call a helper function, e.g., `dfs(graph, colors, i, 1)`, assigning it an initial color (e.g., 1).
*   If the `dfs` call ever returns `false`, it means a conflict was found in that component, so the graph is not bipartite. Return `false` immediately.
*   The `dfs(node, color)` helper function:
    *   Assign the given `color` to the current `node` by setting `colors[node] = color`.
    *   For each `neighbor` of the current `node`:
        *   If the `neighbor` is uncolored (`colors[neighbor] == 0`), recursively call `dfs` on it with the opposite color: `dfs(graph, colors, neighbor, -color)`. If this recursive call returns `false`, propagate the `false` result up.
        *   If the `neighbor` is already colored, check if its color is the same as the current node's color (`colors[neighbor] == color`). If it is, a conflict is found, so return `false`.
*   If the main loop finishes without any `dfs` call returning `false`, it means all components were successfully two-colored. Return `true`.

## Breadth-First Search (BFS) with Two-Coloring
This approach uses an iterative Breadth-First Search (BFS) traversal. Similar to the DFS method, it attempts to color the graph's nodes with two alternating colors. We use a queue to manage the nodes to visit. When we process a node, we color its uncolored neighbors with the opposite color and add them to the queue. If we find a neighbor that is already colored with the same color as the current node, we've detected a conflict (an odd-length cycle), and the graph is not bipartite. This process is repeated for all disconnected components of the graph.
**Time:** O(V + E), where V is the number of vertices and E is the number of edges. Each vertex is enqueued and dequeued at most once, and every edge is examined once. · **Space:** O(V), where V is the number of vertices. This space is required for the `colors` array and the `Queue`. In the worst case, the queue can hold up to O(V) nodes (e.g., in a star graph).
**Pros:** Avoids recursion, thus preventing any potential for stack overflow errors, making it more robust for very large or deep graphs.; Optimal time and space complexity.; Often slightly faster in practice than recursive DFS due to lower overhead from function calls.
**Cons:** The iterative logic using a queue might be slightly more complex to write for some developers compared to the recursive DFS approach.
### Explanation
We maintain a `colors` array, where `0` indicates an uncolored node, `1` represents color A, and `-1` represents color B. We also use a `Queue` for the BFS traversal.
The algorithm iterates through all nodes to handle potentially disconnected graphs. If a node is uncolored, we start a BFS traversal from it:
1.  Assign an initial color (e.g., 1) to the starting node and add it to the queue.
2.  While the queue is not empty, dequeue a node `u`.
3.  For each `neighbor` `v` of `u`:
    *   If `v` is uncolored (`colors[v] == 0`), assign it the opposite color of `u` (`-colors[u]`) and enqueue it.
    *   If `v` is already colored and `colors[v] == colors[u]`, it means two adjacent nodes have the same color. This is a conflict, so we return `false`.
4.  If the BFS for a component completes without any conflicts, we continue the main loop.
If the entire loop finishes without returning `false`, the graph is bipartite.
```java
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] colors = new int[n]; // 0: uncolored, 1: color A, -1: color B

        for (int i = 0; i < n; i++) {
            if (colors[i] == 0) { // This node belongs to a component we haven't visited yet
                Queue<Integer> queue = new LinkedList<>();
                queue.add(i);
                colors[i] = 1; // Start coloring with color 1

                while (!queue.isEmpty()) {
                    int node = queue.poll();
                    for (int neighbor : graph[node]) {
                        if (colors[neighbor] == 0) {
                            // If neighbor is uncolored, color with opposite color and add to queue
                            colors[neighbor] = -colors[node];
                            queue.add(neighbor);
                        } else if (colors[neighbor] == colors[node]) {
                            // If neighbor has the same color, conflict found
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}
```
### Algorithm
*   Initialize a `colors` array of size `n` with `0`s (uncolored).
*   Iterate through each node `i` from `0` to `n-1`.
*   If node `i` is uncolored (`colors[i] == 0`), start a BFS traversal for this component.
    *   Create a `Queue` and add `i` to it.
    *   Color the starting node `i` with an initial color, e.g., `colors[i] = 1`.
    *   While the queue is not empty:
        *   Dequeue a node, let's call it `u`.
        *   For each `neighbor` `v` of `u`:
            *   If `v` is uncolored (`colors[v] == 0`), color it with the opposite color of `u` (`colors[v] = -colors[u]`) and enqueue `v`.
            *   If `v` is already colored, check if its color is the same as `u`'s (`colors[v] == colors[u]`). If so, a conflict exists, and the graph is not bipartite. Return `false`.
*   If the main loop completes without finding any conflicts, it means all components are bipartite. Return `true`.

# Solutions
### Java

```java
class Solution {
private
  int[] color;
private
  int[][] g;
public
  boolean isBipartite(int[][] graph) {
    int n = graph.length;
    color = new int[n];
    g = graph;
    for (int i = 0; i < n; ++i) {
      if (color[i] == 0 && !dfs(i, 1)) {
        return false;
      }
    }
    return true;
  }
private
  boolean dfs(int u, int c) {
    color[u] = c;
    for (int v : g[u]) {
      if (color[v] == 0) {
        if (!dfs(v, 3 - c)) {
          return false;
        }
      } else if (color[v] == c) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isBipartite(vector<vector<int>> &graph) {
    int n = graph.size();
    vector<int> color(n);
    for (int i = 0; i < n; ++i)
      if (!color[i] && !dfs(i, 1, color, graph))
        return false;
    return true;
  }
  bool dfs(int u, int c, vector<int> &color, vector<vector<int>> &g) {
    color[u] = c;
    for (int &v : g[u]) {
      if (!color[v]) {
        if (!dfs(v, 3 - c, color, g))
          return false;
      } else if (color[v] == c)
        return false;
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool: def dfs(u, c): color[u] = c for v in graph[u]: if not color[v]: if not dfs(v, 3 - c): return False elif color[v] == c: return False return True n = len(graph) color = [0] * n for i in range(n): if not color[i] and not dfs(i, 1): return False return True

```