Builds on Flood Fill, which you haven’t finished yet.
Bipartite Graph (Two-Coloring)
You're given an undirected graph on n nodes (numbered 0 to n - 1) as an adjacency list graph, where graph[u] lists every node u shares an edge with. There are no self-loops, no duplicate edges, edges are listed symmetrically on both endpoints, and the graph doesn't need to be one connected piece.
Decide whether the nodes can be split into two groups A and B such that no edge ever connects two nodes in the same group — i.e., whether the graph is bipartite.
Return true if such a split exists, false otherwise.
0, 1 and 2 are all linked to each other in a triangle. Whichever way you split them into two groups, two of them land in the same group while sharing an edge.Bipartite Check
graph ➔ alternate side per edge ➔ valid split or conflict| 1 | from collections import deque |
| 2 | from typing import List |
| 3 | |
| 4 | def is_bipartite(graph: List[List[int]]) -> bool: |
| 5 | """Is Graph Bipartite?: two-color every component with BFS; a clash means an odd |
| 6 | cycle. |
| 7 | Time: O(V + E) | Space: O(V) |
| 8 | """ |
| 9 | # color[node] is -1 (no side yet), 0 or 1 once a component's BFS reaches it |
| 10 | color = [-1] * len(graph) |
| 11 | # 1. Start A Search From Every Uncolored Node: |
| 12 | # The graph may be disconnected, so a node no earlier component's search reached |
| 13 | # still needs its own |
| 14 | # BFS to be colored. |
| 15 | for start in range(len(graph)): |
| 16 | if color[start] != -1: |
| 17 | continue |
| 18 | color[start] = 0 # either side works for the first node of a new component |
| 19 | queue = deque([start]) |
| 20 | # 2. Two-Color The Component With BFS, Checking For A Clash: |
| 21 | # A neighbour with no side yet is forced onto the opposite side of the node that |
| 22 | # reached it; a |
| 23 | # neighbour already on the same side as node means the edge between them closes |
| 24 | # an odd-length |
| 25 | # cycle, which makes a valid two-way split impossible. |
| 26 | while queue: |
| 27 | node = queue.popleft() |
| 28 | for nxt in graph[node]: |
| 29 | if color[nxt] == -1: |
| 30 | color[nxt] = 1 - color[node] |
| 31 | queue.append(nxt) |
| 32 | elif color[nxt] == color[node]: |
| 33 | return False |
| 34 | return True |
color is -1 until the search first reaches it and is never changed after, and every edge checked so far joins a side-0 node to a side-1 node.In a two-group split, a node's side decides the side of each of its neighbours, so the first node of a component takes color[start] = 0 and every neighbour BFS reaches with no side yet takes color[nxt] = 1 - color[node]. Every color is then forced by that first choice and equals the parity of the node's distance from start, so the only way to fail is a neighbour that already has a side with color[nxt] == color[node]: the two paths from start plus that edge close a loop of odd length, and going around an odd loop the sides can't alternate and land back where they began, so return False is right; if no edge ever clashes, sides 0 and 1 are the two groups. The trap is coloring from node 0 only: the graph may be disconnected, so loop for start in range(len(graph)) and start a new search at every node still at color[start] == -1, or an odd cycle in a component that doesn't touch node 0 is never checked.
See it run
Is Graph Bipartite? with a two-side check, step by step
color [-1, -1, -1, -1, -1, -1, -1, -1]
Each circle is a node. The tag under it is its side. The row under the graph is queue: the left box leaves first.
popthe node just taken from queueside 0the node has side 0side 1the node has side 1clashan edge whose two ends have the same side
The graph has 8 nodes. color starts as 8 copies of -1, so no node has a side yet.
Gotcha 1 of 4
- The trap
Gotcha 1: Starting the search from node 0 only
Mistakefor start in [0]:Fixfor start in range(len(graph)):What happens: The graph may be disconnected. A search from node 0 colors only the nodes that node 0 can reach. An odd cycle in another component is then never checked. Looping over every
startbegins a new search at each node that still hascolor[start] == -1.Example: Is Graph Bipartite? (LC 785): graph = [[], [2, 3], [1, 3], [1, 2]]Mistake: returns TrueFix: returns False
- Edges arrive one at a time and you need the first one that joins two nodes already connected, as in Redundant Connection (LC 684): the question is which group a node belongs to, not which side of an edge it sits on. See Union-Find
- You only have to count or explore the connected groups, as in Number of Provinces (LC 547): no edge says its two ends must land in different groups. See Flood Fill
- The edges have a direction and any cycle breaks the answer, as in Course Schedule (LC 207): two-coloring only catches odd cycles in an undirected graph. See Cycle Detection
Deep Dive
Why the first node decides every other node
A bipartite graph is a graph whose nodes can be split into two groups so that every edge joins one node of each group. No edge may have both ends in the same group. This card calls the groups side 0 and side 1.
Take one component, which is a set of nodes that connect to each other. Give its first node start side 0. Each neighbour of start shares an edge with it, so each neighbour must have side 1. Each neighbour of those nodes must have side 0, and so on. Every side in the component is forced by the first choice.
The forced sides follow a simple rule. A node has side 0 if its distance from start is even. It has side 1 if its distance is odd. BFS (breadth-first search) reaches each node by a shortest path, so color[nxt] = 1 - color[node] gives exactly this rule.
A clash happens when an edge joins two nodes that already have the same side. Both nodes were reached from start, and they have the same parity of distance. The two paths from start plus that one edge make a cycle with an odd number of edges. A cycle with an odd number of edges cannot be split, because the sides would have to alternate around the loop and end on the wrong side.
Example: a loop of four nodes [[1, 3], [0, 2], [1, 3], [0, 2]] gets sides [0, 1, 0, 1], and the answer is True. A triangle gets side 0 for the first node, side 1 for the other two, and then the edge between those two is a clash. The answer is False.
One trace: the clash is in the second component
The board uses 8 nodes in two components. Nodes 0 to 3 are the four-node loop from Is Graph Bipartite? (LC 785). Nodes 4 to 7 are a triangle 4, 5, 6 with node 7 attached to node 6.
The search from node 0 gives color = [0, 1, 0, 1, -1, -1, -1, -1]. It checks 8 neighbour entries and finds no clash. Then the for start loop skips nodes 1, 2 and 3, because they already have sides. Node 4 still has color[4] == -1, so a new search starts there.
Pop node 4, which has side 0. Its neighbours 5 and 6 get side 1. Then pop node 5, which has side 1. Its neighbour 4 has side 0, which is fine. Its neighbour 6 has side 1, the same as node 5. This is the clash, and the function returns False.
Node 7 is never reached. The function stops at the first clash, so it does not need to color the rest.
The trap: starting only from node 0
The loop for start in range(len(graph)) is needed. A graph can have several components, and a BFS from one node only reaches its own component.
On the board graph, a search that starts only at node 0 colors nodes 0 to 3 and returns True. The answer is wrong, because the triangle 4, 5, 6 has an odd cycle that nobody checked. The correct answer is False.
Another example is graph = [[], [2, 3], [1, 3], [1, 2]]. Node 0 has no edges. A search from node 0 reaches nothing else and returns True. The nodes 1, 2 and 3 form a triangle, so the correct answer is False.
A second trap is the starting value. color = [-1] * len(graph) uses -1 for no side. If you fill color with 0, every node already looks colored, if color[start] != -1 skips every node, and the function returns True for every graph. On [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]], the correct answer is False.
The cost, and which problems fit
Each node enters queue once, because a node gets a side the first time it is seen and is never changed. Each edge is looked at twice, once from each end. So the time is O(V + E), where V is the number of nodes and E is the number of edges. color and queue hold one entry per node, so the space is O(V).
Example: the four-node loop has 4 edges. The pops look at 8 neighbour entries in total, which is 2 * E. The count follows the formula.
The same check solves any question of the form "can these items be split into two groups?" Possible Bipartition (LC 886) gives pairs of people who dislike each other. Each pair is an edge, and the answer is True when the people can be split into two groups with no pair inside one group. Only the way you build graph changes.
DFS (depth-first search) works as well as BFS here. In a graph that can be split, both give the same sides when the first node of each component takes side 0. If the edges have directions, as in Course Schedule (LC 207), a different check is needed, because this card detects only odd cycles in an undirected graph.
60-Second Pitch
"The items must split into two groups, and every pair rule says two items go to different groups. So I build a graph with one edge per rule and two-color it. This is the question of whether the graph is bipartite. I loop over every node that has no side yet, because the graph may have several components. I give that node side 0 and run BFS. Each new neighbour gets the opposite side, 1 - color[node]. If a neighbour already has the same side as the node I am looking at, the edge closes a cycle with an odd number of edges, and I return False. If no edge clashes, the two sides are the two groups, and I return True. Each node is pushed once and each edge is looked at twice, so the time is O(V + E) and the space is O(V)."
Common Questions
- Why does an odd cycle make a two-group split impossible?
Going around a cycle, the sides must alternate at every edge. After an even number of edges you are back on the starting side, which is correct. After an odd number of edges you would be back at the start node on the other side, which is a contradiction. So a cycle with an odd number of edges cannot be split.
- Why is it enough to find one edge whose two ends have the same side?
Every side in a component was forced by the first node, so there was no other choice. If one edge joins two nodes with the same side, no other assignment can fix it. The two paths from
startand that edge form a cycle with an odd number of edges.- Can you use DFS and not BFS?
Yes. DFS also gives each new neighbour the opposite side of the node that reached it, and it also compares an already colored neighbour with the current node. Use an explicit stack for a long chain, because a recursive DFS can pass Python's recursion limit.
- What are the time and space complexity?
O(V + E)time and O(V) space. Each node entersqueueonce, and each edge is looked at twice, once from each end.colorandqueuehold one entry per node.- How is this different from union-find?
Union-find joins items that must be in the same group, and it answers which group an item belongs to. Two-coloring splits items into two groups, and the rule is that connected items go to different groups. For a version where edges arrive one at a time, see Redundant Connection (LC 684), which asks for the edge that closes a cycle of any length.
SWE Reasoning
Spot it
- The items must be split into exactly two groups, teams or sets.
- A pair rule says two items must be in different groups: they dislike each other, they conflict, or they cannot share a resource.
- The question can also be phrased as "does the graph have a cycle with an odd number of edges?" The two questions have the same answer.
- The graph is undirected. Each edge works in both directions.
- The input can have several components, so the check must start from every node that has no side yet.
The invariant, step by step
colorstarts as -1 for every node. A node with -1 has no side yet.- The
for startloop finds a node withcolor[start] == -1. It gives that node side 0 and puts it inqueue. - BFS pops
nodefrom the front ofqueue. For each neighbournxtwithcolor[nxt] == -1, it setscolor[nxt] = 1 - color[node]and pushesnxt. - A neighbour that already has a side is compared with
node. Ifcolor[nxt] == color[node], the edge joins two nodes on the same side, and the function returns False. - A side is never changed after it is set, so every edge checked so far joins side 0 and side 1.
- If the loop ends with no clash, every edge was checked from both ends. Side 0 and side 1 are the two groups, and the function returns True.
Traps
- Searching only from node 0. An odd cycle in another component is never checked. Loop over every
startand skip nodes that already have a side. - Filling
colorwith 0. Every node then looks colored,if color[start] != -1skips all of them, and the function returns True for any graph. Use -1. - Giving every new neighbour side 1. The sides must alternate along each edge. Use
color[nxt] = 1 - color[node]. - Comparing with
color[start]. A clash is an edge whose two ends have the same side. Comparecolor[nxt]withcolor[node], the node on the other end of the edge. - Using it on a directed problem. Course Schedule (LC 207) asks about any cycle in a directed graph. Two-coloring detects only odd cycles in an undirected graph.
Practice
Builds on Flood Fill, which you haven’t finished yet.
Bipartite Graph (Two-Coloring)
You're given an undirected graph on n nodes (numbered 0 to n - 1) as an adjacency list graph, where graph[u] lists every node u shares an edge with. There are no self-loops, no duplicate edges, edges are listed symmetrically on both endpoints, and the graph doesn't need to be one connected piece.
Decide whether the nodes can be split into two groups A and B such that no edge ever connects two nodes in the same group — i.e., whether the graph is bipartite.
Return true if such a split exists, false otherwise.
0, 1 and 2 are all linked to each other in a triangle. Whichever way you split them into two groups, two of them land in the same group while sharing an edge.Bipartite Check
graph ➔ alternate side per edge ➔ valid split or conflict| 1 | from collections import deque |
| 2 | from typing import List |
| 3 | |
| 4 | def is_bipartite(graph: List[List[int]]) -> bool: |
| 5 | """Is Graph Bipartite?: two-color every component with BFS; a clash means an odd |
| 6 | cycle. |
| 7 | Time: O(V + E) | Space: O(V) |
| 8 | """ |
| 9 | # color[node] is -1 (no side yet), 0 or 1 once a component's BFS reaches it |
| 10 | color = [-1] * len(graph) |
| 11 | # 1. Start A Search From Every Uncolored Node: |
| 12 | # The graph may be disconnected, so a node no earlier component's search reached |
| 13 | # still needs its own |
| 14 | # BFS to be colored. |
| 15 | for start in range(len(graph)): |
| 16 | if color[start] != -1: |
| 17 | continue |
| 18 | color[start] = 0 # either side works for the first node of a new component |
| 19 | queue = deque([start]) |
| 20 | # 2. Two-Color The Component With BFS, Checking For A Clash: |
| 21 | # A neighbour with no side yet is forced onto the opposite side of the node that |
| 22 | # reached it; a |
| 23 | # neighbour already on the same side as node means the edge between them closes |
| 24 | # an odd-length |
| 25 | # cycle, which makes a valid two-way split impossible. |
| 26 | while queue: |
| 27 | node = queue.popleft() |
| 28 | for nxt in graph[node]: |
| 29 | if color[nxt] == -1: |
| 30 | color[nxt] = 1 - color[node] |
| 31 | queue.append(nxt) |
| 32 | elif color[nxt] == color[node]: |
| 33 | return False |
| 34 | return True |
color is -1 until the search first reaches it and is never changed after, and every edge checked so far joins a side-0 node to a side-1 node.In a two-group split, a node's side decides the side of each of its neighbours, so the first node of a component takes color[start] = 0 and every neighbour BFS reaches with no side yet takes color[nxt] = 1 - color[node]. Every color is then forced by that first choice and equals the parity of the node's distance from start, so the only way to fail is a neighbour that already has a side with color[nxt] == color[node]: the two paths from start plus that edge close a loop of odd length, and going around an odd loop the sides can't alternate and land back where they began, so return False is right; if no edge ever clashes, sides 0 and 1 are the two groups. The trap is coloring from node 0 only: the graph may be disconnected, so loop for start in range(len(graph)) and start a new search at every node still at color[start] == -1, or an odd cycle in a component that doesn't touch node 0 is never checked.
See it run
Is Graph Bipartite? with a two-side check, step by step
color [-1, -1, -1, -1, -1, -1, -1, -1]
Each circle is a node. The tag under it is its side. The row under the graph is queue: the left box leaves first.
popthe node just taken from queueside 0the node has side 0side 1the node has side 1clashan edge whose two ends have the same side
The graph has 8 nodes. color starts as 8 copies of -1, so no node has a side yet.
Gotcha 1 of 4
- The trap
Gotcha 1: Starting the search from node 0 only
Mistakefor start in [0]:Fixfor start in range(len(graph)):What happens: The graph may be disconnected. A search from node 0 colors only the nodes that node 0 can reach. An odd cycle in another component is then never checked. Looping over every
startbegins a new search at each node that still hascolor[start] == -1.Example: Is Graph Bipartite? (LC 785): graph = [[], [2, 3], [1, 3], [1, 2]]Mistake: returns TrueFix: returns False
- Edges arrive one at a time and you need the first one that joins two nodes already connected, as in Redundant Connection (LC 684): the question is which group a node belongs to, not which side of an edge it sits on. See Union-Find
- You only have to count or explore the connected groups, as in Number of Provinces (LC 547): no edge says its two ends must land in different groups. See Flood Fill
- The edges have a direction and any cycle breaks the answer, as in Course Schedule (LC 207): two-coloring only catches odd cycles in an undirected graph. See Cycle Detection
Deep Dive
Why the first node decides every other node
A bipartite graph is a graph whose nodes can be split into two groups so that every edge joins one node of each group. No edge may have both ends in the same group. This card calls the groups side 0 and side 1.
Take one component, which is a set of nodes that connect to each other. Give its first node start side 0. Each neighbour of start shares an edge with it, so each neighbour must have side 1. Each neighbour of those nodes must have side 0, and so on. Every side in the component is forced by the first choice.
The forced sides follow a simple rule. A node has side 0 if its distance from start is even. It has side 1 if its distance is odd. BFS (breadth-first search) reaches each node by a shortest path, so color[nxt] = 1 - color[node] gives exactly this rule.
A clash happens when an edge joins two nodes that already have the same side. Both nodes were reached from start, and they have the same parity of distance. The two paths from start plus that one edge make a cycle with an odd number of edges. A cycle with an odd number of edges cannot be split, because the sides would have to alternate around the loop and end on the wrong side.
Example: a loop of four nodes [[1, 3], [0, 2], [1, 3], [0, 2]] gets sides [0, 1, 0, 1], and the answer is True. A triangle gets side 0 for the first node, side 1 for the other two, and then the edge between those two is a clash. The answer is False.
One trace: the clash is in the second component
The board uses 8 nodes in two components. Nodes 0 to 3 are the four-node loop from Is Graph Bipartite? (LC 785). Nodes 4 to 7 are a triangle 4, 5, 6 with node 7 attached to node 6.
The search from node 0 gives color = [0, 1, 0, 1, -1, -1, -1, -1]. It checks 8 neighbour entries and finds no clash. Then the for start loop skips nodes 1, 2 and 3, because they already have sides. Node 4 still has color[4] == -1, so a new search starts there.
Pop node 4, which has side 0. Its neighbours 5 and 6 get side 1. Then pop node 5, which has side 1. Its neighbour 4 has side 0, which is fine. Its neighbour 6 has side 1, the same as node 5. This is the clash, and the function returns False.
Node 7 is never reached. The function stops at the first clash, so it does not need to color the rest.
The trap: starting only from node 0
The loop for start in range(len(graph)) is needed. A graph can have several components, and a BFS from one node only reaches its own component.
On the board graph, a search that starts only at node 0 colors nodes 0 to 3 and returns True. The answer is wrong, because the triangle 4, 5, 6 has an odd cycle that nobody checked. The correct answer is False.
Another example is graph = [[], [2, 3], [1, 3], [1, 2]]. Node 0 has no edges. A search from node 0 reaches nothing else and returns True. The nodes 1, 2 and 3 form a triangle, so the correct answer is False.
A second trap is the starting value. color = [-1] * len(graph) uses -1 for no side. If you fill color with 0, every node already looks colored, if color[start] != -1 skips every node, and the function returns True for every graph. On [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]], the correct answer is False.
The cost, and which problems fit
Each node enters queue once, because a node gets a side the first time it is seen and is never changed. Each edge is looked at twice, once from each end. So the time is O(V + E), where V is the number of nodes and E is the number of edges. color and queue hold one entry per node, so the space is O(V).
Example: the four-node loop has 4 edges. The pops look at 8 neighbour entries in total, which is 2 * E. The count follows the formula.
The same check solves any question of the form "can these items be split into two groups?" Possible Bipartition (LC 886) gives pairs of people who dislike each other. Each pair is an edge, and the answer is True when the people can be split into two groups with no pair inside one group. Only the way you build graph changes.
DFS (depth-first search) works as well as BFS here. In a graph that can be split, both give the same sides when the first node of each component takes side 0. If the edges have directions, as in Course Schedule (LC 207), a different check is needed, because this card detects only odd cycles in an undirected graph.
60-Second Pitch
"The items must split into two groups, and every pair rule says two items go to different groups. So I build a graph with one edge per rule and two-color it. This is the question of whether the graph is bipartite. I loop over every node that has no side yet, because the graph may have several components. I give that node side 0 and run BFS. Each new neighbour gets the opposite side, 1 - color[node]. If a neighbour already has the same side as the node I am looking at, the edge closes a cycle with an odd number of edges, and I return False. If no edge clashes, the two sides are the two groups, and I return True. Each node is pushed once and each edge is looked at twice, so the time is O(V + E) and the space is O(V)."
Common Questions
- Why does an odd cycle make a two-group split impossible?
Going around a cycle, the sides must alternate at every edge. After an even number of edges you are back on the starting side, which is correct. After an odd number of edges you would be back at the start node on the other side, which is a contradiction. So a cycle with an odd number of edges cannot be split.
- Why is it enough to find one edge whose two ends have the same side?
Every side in a component was forced by the first node, so there was no other choice. If one edge joins two nodes with the same side, no other assignment can fix it. The two paths from
startand that edge form a cycle with an odd number of edges.- Can you use DFS and not BFS?
Yes. DFS also gives each new neighbour the opposite side of the node that reached it, and it also compares an already colored neighbour with the current node. Use an explicit stack for a long chain, because a recursive DFS can pass Python's recursion limit.
- What are the time and space complexity?
O(V + E)time and O(V) space. Each node entersqueueonce, and each edge is looked at twice, once from each end.colorandqueuehold one entry per node.- How is this different from union-find?
Union-find joins items that must be in the same group, and it answers which group an item belongs to. Two-coloring splits items into two groups, and the rule is that connected items go to different groups. For a version where edges arrive one at a time, see Redundant Connection (LC 684), which asks for the edge that closes a cycle of any length.
SWE Reasoning
Spot it
- The items must be split into exactly two groups, teams or sets.
- A pair rule says two items must be in different groups: they dislike each other, they conflict, or they cannot share a resource.
- The question can also be phrased as "does the graph have a cycle with an odd number of edges?" The two questions have the same answer.
- The graph is undirected. Each edge works in both directions.
- The input can have several components, so the check must start from every node that has no side yet.
The invariant, step by step
colorstarts as -1 for every node. A node with -1 has no side yet.- The
for startloop finds a node withcolor[start] == -1. It gives that node side 0 and puts it inqueue. - BFS pops
nodefrom the front ofqueue. For each neighbournxtwithcolor[nxt] == -1, it setscolor[nxt] = 1 - color[node]and pushesnxt. - A neighbour that already has a side is compared with
node. Ifcolor[nxt] == color[node], the edge joins two nodes on the same side, and the function returns False. - A side is never changed after it is set, so every edge checked so far joins side 0 and side 1.
- If the loop ends with no clash, every edge was checked from both ends. Side 0 and side 1 are the two groups, and the function returns True.
Traps
- Searching only from node 0. An odd cycle in another component is never checked. Loop over every
startand skip nodes that already have a side. - Filling
colorwith 0. Every node then looks colored,if color[start] != -1skips all of them, and the function returns True for any graph. Use -1. - Giving every new neighbour side 1. The sides must alternate along each edge. Use
color[nxt] = 1 - color[node]. - Comparing with
color[start]. A clash is an edge whose two ends have the same side. Comparecolor[nxt]withcolor[node], the node on the other end of the edge. - Using it on a directed problem. Course Schedule (LC 207) asks about any cycle in a directed graph. Two-coloring detects only odd cycles in an undirected graph.