Two Colour Split Check
Problem
An undirected graph is given as a neighbour list, where entry i holds the nodes joined to node i. Decide whether the nodes can be split into two groups so that every edge joins a node in one group to a node in the other. The graph may be disconnected, so every part has to be checked.
Examples
Input: adj = [[1, 3], [0, 2], [1, 3], [0, 2]]
Output: True
Why: the four-node ring alternates between the two groupsInput: adj = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]
Output: False
Why: nodes 0, 1 and 2 form a triangle, and a triangle cannot alternateInput: adj = [[]]
Output: True
Why: edge case, a lone node with no edges satisfies the ruleHints
0 / 3
Think of the two groups as two colours. Once one node has a colour, every neighbour is forced, so the whole component follows from a single free choice.
Spread the forced colours outward from a starting node and look for a contradiction: an edge whose two ends ended up with the same colour.
Colour an uncoloured node, then walk outward from it giving every neighbour the opposite colour. If a neighbour already carries the same colour as the node you came from, stop with a negative answer. Repeat from every still-uncoloured node so disconnected parts are covered too.
Solution
Choosing a colour for one node forces the colour of everything reachable from it, so a traversal that paints each neighbour the opposite colour explores the only possible assignment for that component. A contradiction can only appear as an edge whose ends share a colour, which is checked as each edge is crossed. Restarting from every uncoloured node handles disconnected graphs, since each component gets its own free first choice. Time is O(V + E) and space is O(V).
from collections import deque
def is_two_colourable(adj):
colour = [0] * len(adj) # 0 means unassigned, 1 and -1 are the groups
for start in range(len(adj)):
if colour[start]:
continue # this component was already painted
colour[start] = 1 # the first choice in a component is free
queue = deque([start])
while queue:
node = queue.popleft()
for nb in adj[node]:
if colour[nb] == colour[node]:
return False # an edge inside one group
if colour[nb] == 0:
colour[nb] = -colour[node]
queue.append(nb)
return True
print(is_two_colourable([[1, 3], [0, 2], [1, 3], [0, 2]])) # -> True
print(is_two_colourable([[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]])) # -> False
print(is_two_colourable([[]])) # -> TrueStuck on the idea rather than the code? Bipartite Check covers it.