LeetCode #886 Medium

Possible Bipartition

Given n people and pairs who dislike each other, decide if they can be split into two groups so no two people in the same group dislike each other.

graphbfsdfscoloring

Open on LeetCode ↗

02

Intuition

The trap is assuming everyone forms one connected group and only coloring starting from person 1. The dislikes graph can split into several disconnected pieces, so a fresh BFS or DFS must start from every uncolored person, not just the first. Within each piece, color a person, force every disliked neighbor to the opposite team, and repeat -- exactly the 2-coloring test for bipartiteness. A conflict is found the moment a neighbor is already colored the SAME as the current person, which is impossible to fix and immediately rules out any valid split.

How to spot this pattern

Two-colouring a graph: neighbours must differ, and a conflict proves an odd cycle exists. The outer loop over every vertex handles disconnected components, which is the detail most single-BFS attempts miss.

03

Approach

1

Build the dislikes graph

For every pair [a, b], add an undirected edge -- each dislikes the other, so the adjacency list gets both directions.

2

Color every disconnected group

Loop over every person; if uncolored, that person starts a brand new group (the graph may not be connected). BFS/DFS from there, coloring team A/B and alternating for each newly reached neighbor.

3

Detect the same-color conflict

When a BFS step reaches a neighbor that is already colored, check its color: if it matches the current person's color, two people who dislike each other ended up on the same team -- return false immediately.

04

Solution & live demo

▶1class Solution:
▶2    def possibleBipartition(self, n, dislikes):
▶3        adj = [[] for _ in range(n + 1)]
▶4        for a, b in dislikes:
▶5            adj[a].append(b)
▶6            adj[b].append(a)
▶7        color = [0] * (n + 1)
▶8        for start in range(1, n + 1):
▶9            if color[start]:
▶10                continue
▶11            color[start] = 1
▶12            queue = [start]
▶13            for u in queue:
▶14                for v in adj[u]:
▶15                    if not color[v]:
▶16                        color[v] = -color[u]
▶17                        queue.append(v)
▶18                    elif color[v] == color[u]:
▶19                        return False
▶20        return True

05

Common pitfalls

Colouring from vertex 1 only

✗ Wrong

queue = [1]
# single BFS

✓ Right

for start in range(1, n + 1):
    if color[start]: continue

The dislike graph is often disconnected, so a single traversal leaves whole components uncoloured and their conflicts undetected. Every uncoloured vertex must seed a new traversal.

Using 0 as a colour

✗ Wrong

color = [0] * (n + 1)
color[start] = 0

✓ Right

color[start] = 1
color[v] = -color[u]

0 doubles as "uncoloured", so a vertex painted 0 looks unvisited and gets re-queued or re-painted. Using 1 and −1 keeps the sentinel distinct and makes negation the recolouring operation.

Only checking neighbours that are uncoloured

✗ Wrong

if not color[v]:
    color[v] = -color[u]
    queue.append(v)

✓ Right

elif color[v] == color[u]:
    return False

An already-coloured neighbour is exactly where a conflict shows up. Skipping those cases means the algorithm colours the graph happily and never detects the odd cycle that makes bipartition impossible.

06

Edge cases

Disconnected dislike groups

Outer loop restarts coloring at every uncolored person, not just person 1.

Person with no dislikes

Trivially colored alone; never causes a conflict.

Odd cycle of dislikes (e.g. 1-2-3-1)

Coloring wraps around and forces a same-color conflict -- correctly reported impossible.

n people, zero dislikes pairs

Every person its own group -- always possible.

07

Complexity

Time

O(V + E)

Space

O(V + E)

Each person colored once, each dislike edge checked at most twice.