# Is Graph Bipartite (Leetcode 785) Solution - Coding Interview Question

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:**

Input:graph = [[1,2,3],[0,2],[0,1,3],[0,2]]Output:falseExplanation: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:**

Input:graph = [[1,3],[0,2],[1,3],[0,2]]Output:trueExplanation: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`

.

**Solution:**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

/**
* Intuition: Each node is seperated into two different parties (0, 1). We do a dfs to distinguish the parties.
* If at any moment, we find the party of two adjacent nodes is same, it means we can't divide the graph
* into two different parties. Since there could be interdepency.
* <p>
* So we do a DFS + Party Map.
* Time Complexity: O(N+E) : N is the number of nodes in graph, E is the number of edges
* Space Complexity: O(N)
**/
class Solution {
public boolean isBipartite(int[][] graph) {
Set<Integer> visited = new HashSet<>();
for (int i = 0; i < graph.length; i++) {
dfs(graph, i, visited, new HashMap<>());
if (!res) {
return res;
}
}
return true;
}
boolean res = true;
void dfs(int[][] graph, int i, Set<Integer> visited, Map<Integer, Integer> party) {
if (visited.contains(i)) {
return;
}
visited.add(i);
for (int j = 0; j < graph[i].length; j++) {
int x = i;
int y = graph[i][j];
Integer a = party.get(x);
Integer b = party.get(y);
if (a == null && b == null) {
party.put(x, 0);
party.put(y, 1);
} else if (a == null && b != null) {
party.put(x, (b + 1) % 2);
} else if (a != null && b == null) {
party.put(y, (a + 1) % 2);
} else if (a != null && b != null) {
if (a.equals(b)) {
res = false;
return;
}
}
dfs(graph, y, visited, party);
}
}
}