Possible Bipartition — Bipartite Graph Check with BFS, DFS, and Union Find

Problem Statement#

There are n people labeled from 1 to n. You are given a list dislikes where each entry [a, b] means person a and person b mutually dislike each other. Decide whether you can split the n people into two groups so that nobody is in the same group as a person they dislike. Return true if such a partition exists, false otherwise.

This problem reduces directly to bipartite testing on the dislikes graph: people are nodes, dislikes are undirected edges, and a valid partition is a 2-coloring such that adjacent nodes have different colors.

Why This Problem Matters#

Possible Bipartition is a textbook bipartite test wrapped in a friendly story. It appears at Amazon, Google, Facebook, and Bloomberg interviews because it tests three skills at once: graph modeling (turning a relationship list into an adjacency structure), BFS or DFS traversal across multiple connected components, and 2-coloring with cycle detection. It is also a stepping stone to harder partition problems such as Possible Bipartition with weights, Course Schedule, and Conflict Graph Coloring.

The problem is also a classic Union Find showcase. Two equivalent approaches solve it cleanly: BFS or DFS coloring, and Union Find with the trick of unioning all enemies of a into a single group, then checking that a is not in the same group as its enemies.

The Core Insight#

A graph is bipartite if and only if it contains no odd-length cycle. Equivalently, a graph is bipartite if you can 2-color it (assign each node one of two colors) such that every edge connects nodes of opposite colors. If during a BFS or DFS coloring you discover a neighbor already colored the same as the current node, you have found an odd cycle and the graph is not bipartite.

The dislikes graph may be disconnected. You must launch a fresh coloring traversal from every uncolored node so that no component is missed. Within each component, the coloring is forced once the first node is colored arbitrarily; either every coloring choice for that component is consistent or the component is not bipartite.

The Union Find variant uses a clever trick: for each a, union all of a's enemies together. If at the end a shares a parent with any of its enemies, the graph is not bipartite. This works because all enemies of a must be in the same group as each other (the group opposite to a).

Visual Dry Run (BFS/DFS trace)#

Take n equal to 4 and dislikes equal to [[1, 2], [1, 3], [2, 4]]. Adjacency: 1 with neighbors 2 and 3, 2 with neighbors 1 and 4, 3 with neighbor 1, 4 with neighbor 2. We use a color map.

Outer loop, i equal to 1. Color is empty for 1. Set color[1] to 0. Push 1 to the queue.

Pop 1. Neighbor 2 uncolored, set color[2] to 1, push 2. Neighbor 3 uncolored, set color[3] to 1, push 3.

Pop 2. Neighbor 1 already colored 0, opposite to 2's color 1, fine. Neighbor 4 uncolored, set color[4] to 0, push 4.

Pop 3. Neighbor 1 colored 0, fine.

Pop 4. Neighbor 2 colored 1, fine.

Outer loop, i equal to 2, 3, 4. Already colored, skip.

Return true. Group 0 contains persons 1 and 4. Group 1 contains persons 2 and 3. No dislike pair is within a group.

Now consider dislikes equal to [[1, 2], [1, 3], [2, 3]], which forms a triangle.

BFS from 1. Color 1 zero. Color 2 one. Color 3 one. When we pop 2, neighbor 3 already colored 1, same as 2's color 1. Return false. The triangle has an odd cycle, so it is not bipartite.

Solution (Optimal)#

Python — BFS 2-coloring#

from collections import deque, defaultdict
 
class Solution:
    def possibleBipartition(self, n, dislikes):
        adj = defaultdict(list)
        for u, v in dislikes:
            adj[u].append(v)
            adj[v].append(u)
        color = {}
        for i in range(1, n + 1):
            if i in color:
                continue
            q = deque([i])
            color[i] = 0
            while q:
                node = q.popleft()
                for nb in adj[node]:
                    if nb not in color:
                        color[nb] = 1 - color[node]
                        q.append(nb)
                    elif color[nb] == color[node]:
                        return False
        return True

JavaScript — DFS 2-coloring#

var possibleBipartition = function(n, dislikes) {
    const adj = Array.from({ length: n + 1 }, () => []);
    for (const [a, b] of dislikes) {
        adj[a].push(b);
        adj[b].push(a);
    }
    const color = new Array(n + 1).fill(-1);
    const dfs = (node, c) => {
        color[node] = c;
        for (const nb of adj[node]) {
            if (color[nb] === -1) {
                if (!dfs(nb, 1 - c)) return false;
            } else if (color[nb] === c) {
                return false;
            }
        }
        return true;
    };
    for (let i = 1; i <= n; i++) {
        if (color[i] === -1 && !dfs(i, 0)) return false;
    }
    return true;
};

Time complexity is O(V plus E) for both BFS and DFS, where V equals n and E equals the number of dislike pairs. Space is O(V plus E) for the adjacency list and O(V) for the color map plus traversal stack or queue.

Common Mistakes#

Forgetting to add edges in both directions when the relationship is symmetric leaves half the dislikes invisible. Skipping the outer for-loop and only running BFS from node 1 misses disconnected components, returning incorrect true on graphs where component A is bipartite but component B is not. Coloring the start node before checking if it is already colored leads to repeat traversals. Returning early at the first uncolored neighbor without recursing wastes time; the coloring conflict can occur deeper in the component. Using strict equality on integer color values 0 and 1 with implicit conversions in some languages can mis-match; stick with explicit comparisons.

Interview Tips#

Open by translating the problem into bipartite-graph language; this signals graph fluency. State the coloring invariant: every edge must connect different colors. Explicitly mention that the graph may be disconnected and that you launch a fresh coloring from every uncolored node. Discuss both BFS and DFS variants; pick BFS in production code to avoid stack overflow on chains, but DFS is shorter on a whiteboard. Mention the Union Find alternative as a follow-up to demonstrate breadth.

Follow-up Questions#

How would Union Find solve this? For each person a, union together all of a's enemies. After processing every person, if any enemy of a shares a root with a, the graph is not bipartite. The complexity is near-linear with path compression. What if dislikes are weighted or have priorities? You enter the realm of weighted bipartite matching, which Hungarian algorithm handles. What if the graph is enormous and stored in a database? Use external BFS that streams adjacency from disk and persists colors in a key-value store. How do you list the two groups when bipartite? Just collect nodes by color value at the end.

Key Takeaways#

• Possible Bipartition reduces to a bipartite test on the dislikes graph
• A graph is bipartite if and only if it contains no odd-length cycles
• BFS or DFS 2-coloring runs in O(V plus E); always loop over all components
• Union Find offers an alternative by unioning enemies of each node
• Build the adjacency list with both directions because dislikes are mutual
• Pattern unlocks Is Graph Bipartite, Course Schedule, and Conflict Graph Coloring