is graph bipartitie

🏠

credit: daciuk

 1 class 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 
14 assert Solution().isBipartite([[1, 3], [0, 2], [1, 3], [0, 2]])
15 assert Solution().isBipartite([[1, 5], [0, 2], [1, 3], [2, 4], [3, 5], [0, 4]])
16 assert Solution().isBipartite([[1, 2], [0, 2], [0, 1]]) == False
17 assert (
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 )