Is Graph Bipartite?
Given an undirected graph
, return true
if and only if it is bipartite.
Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.
The graph is given in the following form: graph[i]
is a list of indexes j
for which the edge between nodes i
and j
exists. Each node is an integer between 0
and graph.length - 1
. There are no self edges or parallel edges: graph[i]
does not contain i
, and it doesn't contain any element twice.
Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation:
The graph looks like this:
0----1
| |
| |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation:
The graph looks like this:
0----1
| \ |
| \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.
Note:
graph
will have length in range[1, 100]
.graph[i]
will contain integers in range[0, graph.length - 1]
.graph[i]
will not containi
or duplicate values.The graph is undirected: if any element
j
is ingraph[i]
, theni
will be ingraph[j]
.
class Solution {
// Input is adjacency list
// -1 => Node is not colored yet
// 0 => lets say color blue
// 1 => lets say color green
public boolean isBipartite(int[][] graph) {
int[] color = new int[graph.length];
Arrays.fill(color, -1);
for (int i = 0; i < graph.length; i++)
// Node is uncolored and the result from this connected component is false
// i.e => this component is not bi-partite
if ((color[i] == -1) && !bfs(i, graph, color))
return false;
return true;
}
private boolean bfs(int node, int[][] graph, int[] color) {
Queue<Integer> q = new LinkedList<>();
q.add(node);
color[node] = 0;
// coloring current node
while (!q.isEmpty()) {
int curr = q.poll();
for (int neighbor : graph[curr]) {
// If neighbour has the same color
if (color[neighbor] == color[curr])
return false;
// If neighbor is uncolored
if (color[neighbor] == -1) {
// coloring with opposite color
color[neighbor] = 1 - color[curr];
q.add(neighbor);
}
}
}
return true;
}
}
Last updated