Can every node get one of two colours so no edge joins a matching pair? Paint each component by BFS and stop at the first clash.
▼The problem
LeetCode 785 (Medium). Given an undirected graph as an adjacency list graph[u], return true if its nodes can be split into two sets so that every edge joins a node in one set to a node in the other. The graph may be disconnected.
Examples (LeetCode's): graph = [[1,2,3],[0,2],[0,1,3],[0,2]] → false (0, 1 and 2 form a triangle) and graph = [[1,3],[0,2],[1,3],[0,2]] → true (sets {0, 2} and {1, 3}).
The solution
def isBipartite(graph):
color = [-1] * len(graph)
for start in range(len(graph)):
if color[start] != -1: continue
color[start] = 0
queue = deque([start])
while queue:
u = queue.popleft()
for v in graph[u]:
if color[v] == -1:
color[v] = 1 - color[u]
queue.append(v)
elif color[v] == color[u]:
return False
return TrueTranscript
Is Graph Bipartite? Given an undirected graph as adjacency lists, can you split its nodes into two teams so every edge joins the two teams?
Take a square: zero links to one and three, and two links to one and three. Give zero and two orange scarves, and one and three blue. Every edge crosses, so true. Now add the diagonal from zero to two. Zero, one and two form a triangle, which can't be split. False.
The naive way tries all two to the n splits and checks every edge each time. Four nodes is sixteen splits; thirty nodes is over a billion.
Better: hand out scarves as you go. Give an unscarved node orange, then visit its neighbours breadth first, giving each the opposite colour. If a neighbour already wears your colour, that's a clash, an odd cycle: return false. Loop over every node, so separate pieces get scarves too.
In code, a colour array starts empty, and a queue spreads colours from each uncoloured start. Union-find also works: merge each node's neighbours, and fail if a node shares their set.
Let's run both. On the square, zero is orange, one and three turn blue, then two turns orange. No clash: true. With the diagonal, one, two and three all turn blue. Then one checks two: both blue. Clash! False.
Each node is queued once and each edge is checked from both ends: order V plus E time, and order V space.
Two colours, flip across every edge, stop at a clash. That's Is Graph Bipartite.