Possible Bipartition: Graph Two-Coloring with BFS

You are given n people labeled 1 through n, along with a list of pairs who dislike each other. Your job is to split everyone into two groups so that no two people in the same group dislike each other. If you can do it, return true. If not, return false.

This is LeetCode 886: Possible Bipartition, and it is really a graph coloring problem in disguise. Each person is a node, each dislike pair is an undirected edge, and the question is whether the graph is bipartite: can you two-color the nodes so that every edge connects nodes of different colors?

Why this problem matters

Bipartite graphs appear constantly in computer science. A bipartite graph is one where you can divide all nodes into two sets such that every edge goes between the sets, never within a set. Scheduling conflicts, matching problems, and dependency checks all reduce to bipartite testing.

The two-coloring approach is the standard way to check for bipartiteness. If you can assign every node one of two colors such that no two adjacent nodes share the same color, the graph is bipartite. If at any point you are forced to give two adjacent nodes the same color, it is not. This directly connects to the classic theorem: a graph is bipartite if and only if it contains no odd-length cycles.

Understanding this problem gives you the foundation for more advanced graph problems like maximum bipartite matching, flow networks, and constraint satisfaction. It also reinforces BFS/DFS traversal patterns that you will use over and over in interviews.

The two-coloring approach

Think of it like painting a map. Start at any unvisited node and paint it red. Then paint all its neighbors blue. Then paint all their unvisited neighbors red. Keep alternating. If you ever need to paint a node that is already painted the wrong color, the graph is not bipartite.

BFS is a natural fit because it processes nodes level by level. Nodes at even levels get one color, nodes at odd levels get the other. You can also use DFS with the same coloring logic. Both work.

The algorithm:

1. Build an adjacency list from the dislikes array.
2. For each unvisited node, start a BFS. Assign it color 0.
3. For every neighbor, if uncolored, assign the opposite color and enqueue it. If already colored with the same color as the current node, return false.
4. If BFS finishes without conflict for all components, return true.

The outer loop over all nodes is essential. The graph might be disconnected (some people have no dislikes at all), and you need to check every connected component separately.

Clean solution

from collections import deque

def possible_bipartition(n: int, dislikes: list[list[int]]) -> bool:
    graph: dict[int, list[int]] = {i: [] for i in range(1, n + 1)}
    for a, b in dislikes:
        graph[a].append(b)
        graph[b].append(a)

    color = [0] * (n + 1)

    for node in range(1, n + 1):
        if color[node] != 0:
            continue

        queue = deque([node])
        color[node] = 1

        while queue:
            curr = queue.popleft()
            for neighbor in graph[curr]:
                if color[neighbor] == 0:
                    color[neighbor] = -color[curr]
                    queue.append(neighbor)
                elif color[neighbor] == color[curr]:
                    return False

    return True

Complexity analysis

V is the number of people, E is the number of dislike pairs.

Time: Building the adjacency list is O(E). BFS visits every node once and processes every edge once. Total: O(V + E).

Space: The adjacency list stores 2E entries (each undirected edge appears twice). The color array is O(V). The BFS queue holds at most O(V) nodes. Total: O(V + E).

Edge cases to watch for

• No dislikes: dislikes = []. Everyone can go in one group. Return true.
• Two people who dislike each other: the simplest case. Put them in different groups. Always works.
• Odd cycle: three people A, B, C where A dislikes B, B dislikes C, and C dislikes A. You cannot two-color a triangle. Return false.
• Disconnected components: some people have no edges. Check each connected component independently. A disconnected person can go in either group.
• Self-dislike is not possible: the problem guarantees 1 <= dislikes[i][0], dislikes[i][1] <= n and the two entries differ. No need to handle self-loops.
• Duplicate dislike pairs: the problem may include duplicate pairs. The algorithm handles this naturally since re-visiting an already-colored node just triggers the conflict check.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently:

1. BFS graph traversal with adjacency list

The pattern of building a graph from an edge list and traversing it level by level:

graph = {i: [] for i in range(n)}
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

visited = set()
queue = deque([start])
visited.add(start)

while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

This is the same BFS skeleton you see in Number of Islands and Course Schedule. The only twist here is that instead of a simple visited set, you track color assignments.

2. Two-coloring (bipartite check)

The pattern of assigning alternating labels during traversal:

color[neighbor] = -color[curr]

Using 1 and -1 as the two colors makes the "assign opposite" logic trivial: just negate. This same trick works for any problem where you need to alternate between two states during BFS or DFS.

From understanding to recall

You have read through the BFS two-coloring solution and traced the steps visually. The logic is clear: color a node, color its neighbors the opposite, check for conflicts. But writing it from scratch under pressure is different from reading it.

The small details matter. Using 1 and -1 for clean negation. Checking color[neighbor] == color[curr] instead of just color[neighbor] != 0. Looping over all nodes to handle disconnected components. These are the things that trip people up when the clock is ticking.

Spaced repetition turns reading comprehension into writing fluency. You practice building the adjacency list and the BFS coloring loop from memory at increasing intervals. After a few rounds, the pattern flows out naturally. You do not need to re-derive it. You just write it.

Related posts

• Number of Islands - BFS/DFS graph traversal on a grid
• Is Graph Bipartite? - The direct prerequisite problem for bipartite checking
• Course Schedule - Another graph problem using BFS for cycle detection

CodeBricks breaks Possible Bipartition into its adjacency-list-construction and BFS-two-coloring building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a graph coloring problem shows up in your interview, you do not hesitate. You just write it.