Possible Bipartition

Intuition

Treat every person as a node and every dislike as an undirected edge connecting two people who must be separated. Splitting people into two groups is exactly asking whether this dislike graph is bipartite. So we try to paint the graph with two colors so that no edge joins two same-colored nodes. Running a BFS from each unpainted person and alternating colors along edges detects any conflict: if a dislike ever links two people already in the same group, no valid split exists.

Algorithm walkthrough

1. 1Build an adjacency list of size n + 1 and add both directions for each dislike pair (people are 1-indexed).
2. 2Create a color array; 0 means unassigned, and we alternate between +1 and -1 for the two groups.
3. 3For every person from 1 to n that is still unassigned, color them +1 and start a BFS.
4. 4Pop a person and scan their disliked neighbors: assign an unassigned neighbor the opposite color and enqueue it.
5. 5If a neighbor already holds the same color as the current person, return false - a dislike sits inside one group.
6. 6If all components color cleanly, the two-group split works, so return true.

Implementation

from collections import deque
from typing import List

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        adj = [[] for _ in range(n + 1)]
        for a, b in dislikes:
            adj[a].append(b)
            adj[b].append(a)
        color = [0] * (n + 1)
        for start in range(1, n + 1):
            if color[start] != 0:
                continue
            color[start] = 1
            queue = deque([start])
            while queue:
                node = queue.popleft()
                for neighbor in adj[node]:
                    if color[neighbor] == 0:
                        color[neighbor] = -color[node]
                        queue.append(neighbor)
                    elif color[neighbor] == color[node]:
                        return False
        return True