Bipartite Color Assignment

Problem

Two-color an undirected graph if possible, returning the color of every node.

Process components in increasing start-node order, give each start color 0, and BFS alternating 0/1 across edges. Return the color list when the graph is bipartite, or an empty list as soon as two adjacent nodes must share a color. Neighbors are scanned in sorted order.

Hint

A conflict appears exactly when an already colored neighbor has the same color as the current node.

Test cases

case 1

in: [4,[[0,1],[1,2],[2,3],[3,0]]]

expected: [0,1,0,1]

case 2

in: [3,[[0,1],[1,2],[2,0]]]

expected: []

case 3

in: [4,[[0,1],[2,3]]]

expected: [0,1,0,1]

case 4

in: [5,[]]

expected: [0,0,0,0,0]

case 5

in: [2,[[0,1],[0,1]]]

expected: [0,1]

Starter codePython

def bipartite_coloring(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor