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 trueif and only if it is bipartite.
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.
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}.
from collections import dequeclass Solution: # Time: O(V + E) where V is nodes, E is edges # Space: O(V) def is_bipartite(self, graph: list[list[int]]) -> bool: n = len(graph) color = [-1] * n for start in range(n): if color[start] == -1: queue = deque([start]) color[start] = 0 while queue: node = queue.popleft() for neighbor in graph[node]: if color[neighbor] == -1: color[neighbor] = 1 - color[node] queue.append(neighbor) elif color[neighbor] == color[node]: return False return True
