Possible Bipartition
Possible Bipartition is LeetCode 886 (Medium). There are n people, numbered 1 … n, to be split into two groups of any size. You are given dislikes, where dislikes[i] = [a, b] means person a and person b must not be in the same group.
Return true if it is possible to split everyone into two groups so that no two people who dislike each other share a group, and false otherwise.
- A group may be empty, and people with no dislikes can go in either group.
- Each pair appears at most once.
With up to 2,000 people and 10⁴ dislikes, one linear pass over the graph is enough.
- 1 <= n <= 2000
- 0 <= dislikes.length <= 10⁴
- dislikes[i].length == 2
- 1 <= ai < bi <= n
- All the pairs of dislikes are unique.
Intuition
Turn the people into a graph:
- each person is a vertex;
- each dislike pair is an edge between two vertices.
Splitting into two groups is then two-colouring: give every vertex one of two colours so that no edge joins two vertices of the same colour. A graph that can be coloured this way is a bipartite graph, so possible bipartition asks one question: is the dislike graph bipartite?
Colouring is forced once one vertex is chosen. Put any person in group A; everyone they dislike must go to group B; everyone those people dislike must go to A; and so on. BFS spreads these forced choices outward.
It fails only when an edge joins two vertices that were forced into the same group. That happens exactly when the graph has a cycle of odd length: going round an odd cycle, the colours alternate A, B, A, … and the last vertex ends up the same colour as its neighbour the first.
Split into two sides so that certain pairs are always on opposite sides: bipartite check. The same code solves Is Graph Bipartite? (LeetCode 785), team splitting, and two-colouring a map. With more than two groups the problem becomes general graph colouring, which has no efficient exact algorithm.
Approach
Before reading on: draw the dislike graph for the second example. Colour person 1 blue and follow the rules. Where does it go wrong? Then think about people who dislike nobody, and about groups of people with no link to person 1.
Two ways to solve it
A queue spreads the forced colours outward from each uncoloured person, one layer at a time.
- Depth: no recursion at all.
- Clash check: while scanning each popped person.
- Safe for: a chain of all 2,000 people.
The safer choice in every language.
A recursive helper colours a person, then calls itself on each uncoloured neighbour with the other colour.
- Depth: up to n nested calls.
- Clash check: the same same-colour test.
- Code: a few lines shorter.
In Python, raise the recursion limit first.
Both colour each person once, but BFS never recurses, so a long chain of dislikes cannot overflow the stack. The steps, code and live demo below follow BFS; the DFS code comes after the demo.
Build the dislike graph
An adjacency list over people 1 … n. Each pair [a, b] adds b to adj[a] and a to adj[b]. A dislike goes both ways, so both people need the edge.
Start a BFS from every uncoloured person
Give them colour 1 (group A) and spread from there. Every person still uncoloured after one BFS starts the next. The dislike graph can have several separate groups, and each needs its own starting colour. Starting only from person 1 would leave unconnected people unchecked.
Spread the forced colours
Pop u. For each neighbour v:
- uncoloured: give it
-color[u](the other group) and queue it; - already coloured differently: nothing to do.
In a two-group split, a neighbour's group is forced to be the opposite one.
Stop on a clash
If a neighbour already has the same colour as u, two people who dislike each other are forced into one group: return false. A clash means some cycle has odd length, and no two-group split exists.
Return true
If every component is coloured without a clash, the two colours are the two groups. Every dislike edge now joins two different colours.
Possible Bipartition solution in Python | C++ | Java
DFS colouring
paint(u, c) gives person u colour c, then visits every neighbour: a neighbour with colour c is a clash, and an uncoloured one is painted -c recursively.
Common pitfalls
Only colouring from person 1
color[1] = 1 queue = deque([1]) ...
for start in range(1, n + 1):
if color[start] == 0:
# BFS from startThe dislike graph can be disconnected. With n = 5 and dislikes [[1,2], [3,4], [4,5], [3,5]], BFS from 1 never reaches the triangle 3, 4, 5 and wrongly returns true.
Adding each dislike in one direction only
for a, b in dislikes:
adj[a].append(b)for a, b in dislikes:
adj[a].append(b)
adj[b].append(a)Dislike is mutual, but the graph would only know one direction. For n = 3, [[1,2], [3,1]], person 3 is started on its own, gets colour 1 without ever seeing that 1 already has colour 1, and the check then reports a clash: false, although {1} and {2, 3} work.
Rejecting every cycle
if color[v] != 0:
return False # any revisitif color[v] == color[u]:
return False # same group onlyMeeting an already-coloured person is normal. Four people who dislike in a ring, [[1,2], [2,3], [3,4], [4,1]], split fine into {1, 3} and {2, 4}. Only an edge between two people of the same colour, which comes from an odd cycle, makes it impossible.
Edge cases
Arrays have size n + 1 and index 0 is unused, so person n has a slot.
Complexity
m is the number of dislikes. Each person is coloured and dequeued once, and each dislike is checked twice (once from each end). The adjacency list holds 2m entries.Possible Bipartition FAQ
How do you solve possible bipartition?
- Model: people are vertices, dislikes are undirected edges.
- Goal: 2-colour the graph so no edge joins two equal colours.
- BFS: from every uncoloured person, colour it 1; give each uncoloured neighbour the opposite colour and queue it.
- Fail: if a neighbour already has the same colour, return
false. - Complexity: O(n + m) time and space.
Is possible bipartition the same as Is Graph Bipartite?
Yes, apart from the input format. LeetCode 785 gives the adjacency list directly with vertices from 0; the possible bipartition LeetCode problem (886) gives an edge list of dislikes with people from 1. The colouring algorithm is identical.