LeetCode #785 Is Graph Bipartite?

Problem

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.

Examples

1
2
3
4
5
6
7
8
9
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}.
1
2
3
4
5
6
7
8
9
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.

Solution

Method: Breadth-first Search

Time Complexity: O(V + E)

Space Complexity: O(V + E)

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
class Solution:
def isBipartite(self, graph):
"""
:type graph: List[List[int]]
:rtype: bool
"""
if not graph:
return False

color = {idx: None for idx, _ in enumerate(graph) if graph[idx]}

for node_idx in color:
if color[node_idx] == None:
color[node_idx] = True
dq = collections.deque([node_idx])

while dq:
node = dq.popleft()
node_color = not color[node]

for edge_node in graph[node]:
if color[edge_node] is None:
color[edge_node] = node_color
dq.append(edge_node)
elif color[edge_node] != node_color:
return False

return True

# print(Solution().isBipartite([[]]) == True)
# print(Solution().isBipartite([[1,2,3],[0,2],[0,1,3],[0,2]]) == False)
# print(Solution().isBipartite([[2,4],[2,3,4],[0,1],[1],[0,1],[7],[9],[5],[],[6],[12,14],[],[10],[],[10],[19],[18],[],[16],[15],[23],[23],[],[20,21],[],[],[27],[26],[],[],[34],[33,34],[],[31],[30,31],[38,39],[37,38,39],[36],[35,36],[35,36],[43],[],[],[40],[],[49],[47,48,49],[46,48,49],[46,47,49],[45,46,47,48]]) == False)

Reference

https://www.geeksforgeeks.org/bipartite-graph/