Bipartite graph coloring

Write codeMedium25 min

Your task

Given an undirected graph on n nodes (edges [u, v]), determine if it is bipartite (2-colorable). If it is, return a two-element list [size_color_A, size_color_B] where, summed over connected components, color A gets the larger side of each component and color B the smaller (ties go to A). If the graph is NOT bipartite, return the single-element list [-1]. Isolated nodes form their own component of size 1.

Examples

bipartite_coloring(n: int, edges: list[list[int]]) -> list[int]

Example 1

Inputbipartite_coloring(4, [[0, 1], [1, 2], [2, 3], [3, 0]])

Output[2, 2]