# Is Graph Bipartite? LeetCode Solution

Difficulty Level Medium
Depth First Search GraphViews 140

## Problem Statement

Is Graph Bipartite LeetCode Solution- 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 the set `A` and a node in the set `B`.

Return `true` if and only if it is bipartite.

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

```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}.```

## Approach:

A bipartite graph (or digraph) is a graph whose vertices can be divided into two disjoint and independent sets, that is every edge connects a vertex into one. Vertex sets and. are usually called the parts of the graph. This problem can be easily understood and solved by assuming that each node is a graph that can be colored blue(1), red(0), or none(-1). If after traversal we found even a single node has a different color then the graph is not a bipartite graph. Here we are using the fact that in a bipartite graph no 2 adjacent nodes will be colored with the same color (1 or 0 for example)

We will initialize a list of colors with 0 (by default). Next, we will assign each node with color, either: 1 or -1. Remember that in the bipartite graph, no two adjacent nodes can have the same color.
If we caught two adjacent nodes with the same color, we will return false immediately.

## Code:

### Is Graph Bipartite? C++ Leetcode Solution:

```class Solution {
private:
bool checkIfBipartite(int current, vector<vector<int>> &graph, vector<int> &color) {
if(color[current] == -1)
color[current] = 1;
for(auto it : graph[current]) {
if(color[it] == -1) {
color[it] = 1 - color[current];
if(!checkIfBipartite(it, graph, color))
return false;
} else if(color[it] == color[current])
return false;
}
return true;
}
public:
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> color(n, -1);
for(int i = 0; i < n; ++i) {
if(!checkIfBipartite(i, graph, color))
return false;
}
return true;
}
};```

### Is Graph Bipartite? Java Leetcode Solution:

```class Solution {
private static boolean checkBipartite(int current, int[][] graph, int[] color) {
if(color[current] == -1)
color[current] = 1;
for(int adj : graph[current]) {
if(color[adj] == -1) {
color[adj] = 1 - color[current];
if(checkBipartite(adj, graph, color) == false)
return false;
} else if(color[adj] == color[current])
return false;
}
return true;
}
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int color[] = new int[n];
for(int i = 0; i < n; ++i)
color[i] = -1;
for(int i = 0; i < n; ++i) {
if(checkBipartite(i, graph, color) == false)
return false;
}
return true;
}
}```

## Complexity Analysis for Is Graph Bipartite Leetcode Solution:

### Time Complexity

O(V+E) for doing the standard DFS approach.

### Space Complexity

O(V) for storing the colors array and the auxiliary space required for recursion.

Translate »