An undirected graph on nodes 0 .. n - 1 is given as an adjacency list: graph[u] lists the neighbours of u (no self-loops, no repeated neighbours, and v in graph[u] exactly when u in graph[v]). The graph may be disconnected.
Write is_bipartite(graph) -> bool: can the nodes be split into two sets so that every edge goes between the sets?
is_bipartite([[1, 3], [0, 2], [1, 3], [0, 2]]) # True (square: {0, 2} and {1, 3})
is_bipartite([[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]) # False (0-1-2 is a triangle)
Graphs have up to 100,000 nodes and 100,000 edges and may be one long path, so aim for O(n + edges) and avoid deep recursion.
Show hint
Once you put one node of a connected piece on a side, every other node in that piece is forced; check whether the forced choices ever clash. (A union-find that puts all of a node's neighbours in one set also works.)