1class Solution:
2 def isBipartite(self, graph):
3 cols = {}
4
5 def dfs(u, c):
6 if u in cols:
7 return cols[u] == c
8 cols[u] = c
9 return all(dfs(v, int(1 ^ c)) for v in graph[u])
10
11 return all(dfs(u, 0) for u in range(len(graph)) if u not in cols)
12
13
14assert Solution().isBipartite([[1, 3], [0, 2], [1, 3], [0, 2]])
15assert Solution().isBipartite([[1, 5], [0, 2], [1, 3], [2, 4], [3, 5], [0, 4]])
16assert Solution().isBipartite([[1, 2], [0, 2], [0, 1]]) == False
17assert (
18 Solution().isBipartite(
19 [
20 [],
21 [2, 4, 6],
22 [1, 4, 8, 9],
23 [7, 8],
24 [1, 2, 8, 9],
25 [6, 9],
26 [1, 5, 7, 8, 9],
27 [3, 6, 9],
28 [2, 3, 4, 6, 9],
29 [2, 4, 5, 6, 7, 8],
30 ]
31 )
32 == False
33)