Return true if the undirected graph can be colored with two colors so that no edge
joins two same-colored nodes (i.e. the graph is bipartite).
canColor(graph)
Input format: undirected edges as a,b pairs.
a,b b,c c,d d,a // → true (a 4-cycle is bipartite)
a,b b,c c,a // → false (odd cycle / triangle)
"Two-colorable so no edge connects same-colored nodes" is the definition of bipartite. Can every node sort into one of two buckets so every edge crosses between buckets, never staying inside one?
Checking every possible two-way split is exponential in the number of nodes. You need a constructive way to build a valid coloring (or prove none exists) via forced decisions, not guessing.
Once the first node gets a color, every neighbor is forced to the opposite color — otherwise that edge joins two same-colored nodes. Then their neighbors are forced back, and so on. No freedom of choice after the first pick (and flipping the whole graph's colors just swaps labels).
BFS visits a node's neighbors right after the node, exactly when you need to assign or check their color. Pick an uncolored node, color it, walk its component assigning the opposite color of the node you came from. Reaching an already-colored node: if it matches what you'd assign now, that's a contradiction — return false immediately.
A contradiction only happens with an odd-length cycle. Walking around one, colors alternate 0,1,0,1,... but an odd number of steps forces the last node to clash with the first. Even cycles alternate perfectly and close with no conflict — "bipartite" and "no odd cycle" are the same condition.
Each disconnected piece must be checked independently, starting fresh for every uncolored component — edges never cross components, so one being bipartite says nothing about another. The whole graph is bipartite only if every component 2-colors successfully.
def can_color(graph):
color = {}
for start in graph:
if start in color:
continue
color[start] = 0
queue = [start]
while queue:
node = queue.pop(0)
for nxt in graph.get(node, []):
if nxt in color:
if color[nxt] == color[node]:
return False
else:
color[nxt] = 1 - color[node]
queue.append(nxt)
return True
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.