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.

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

python

▶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

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.

06

Complexity

Time

O(V + E)

Space

O(V + E)

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