Domain 2MediumMEDIUM

Possible Bipartition

Determines if a graph can be partitioned into two sets such that no edges connect nodes within the same set using Breadth-First Search coloring.

Domain: medium•Updated: 2026-09-03
#BFS#Adjacency List#O(N + E)#O(N + E)

Problem Breakdown

We are given NN people (nodes) and a list of “dislike” relationships (edges). If two people dislike each other, they cannot be in the same group. We need to determine if we can partition all nodes into exactly two groups such that no edge connects two nodes within the same group.

  • Inputs:
    • N: Integer representing number of people (1≤N≤20001 \le N \le 2000).
    • dislikes: List of pairs [a,b][a, b] indicating a conflict between person aa and person bb.
  • Outputs: Boolean (True if bipartition is possible, False otherwise).
  • Implicit Constraints & Edge Cases:
    • The graph formed by dislikes may be disconnected (some people have no conflicts with anyone else). We must ensure every component of the graph satisfies the condition.
    • An empty dislikes list implies everyone can go into any group, so it should return True.
    • N=1N=1 is trivially possible since there are no pairs to conflict.

Intuition

This problem maps directly to checking if a graph is Bipartite. A bipartite graph allows nodes to be colored with two colors such that no adjacent nodes share the same color.

  • Brute Force: We could try assigning every person to Group 1 or Group 2 (2N2^N possibilities). For N=2000N=2000, this is computationally impossible (exponential time complexity).
  • Key Insight: Instead of guessing, we can construct the graph and traverse it. If a conflict arises during traversal where two connected nodes are forced into the same group, then no valid partition exists.
  • Optimal Approach: Use Breadth-First Search (BFS) or Depth-First Search (DFS). We maintain an array to track which “group” each person is assigned to (-1 for unassigned, 0 and 1 for groups). As we traverse neighbors of a node, if the neighbor is unvisited, assign it the opposite group. If visited, check that its group matches our requirement (opposite of current).

Approach

  1. Graph Construction: Convert dislikes into an adjacency list representation since NN and edge count are manageable (O(N+E)O(N+E) space), making traversal efficient. Note that dislikes imply a bidirectional relationship: if A dislikes B, B dislikes A.
  2. State Tracking: Initialize a color array of size N+1N+1 with -1 (representing unvisited). We use indices 0 and 1 to represent the two groups.
  3. Traversal Loop: Iterate through every person from 11 to NN. This is crucial because the graph might be disconnected; we must ensure every component of people satisfies the bipartite property, not just those connected via dislikes.
  4. BFS Execution: For each unvisited node encountered:
    • Start a BFS queue with that node assigned Group 0.
    • While processing nodes from the queue, inspect neighbors.
    • If neighbor is unassigned (-1), assign it 1 - current_color and enqueue.
    • If neighbor is already assigned, verify its color differs from current node’s color (color[neighbor] != color[node]).
  5. Conflict Detection: If we find a visited neighbor with the same group assignment as the current node, return False immediately (odd cycle detected).
  6. Completion: If all components are traversed without conflict, return True.

Complexity Analysis

  • Time Complexity: O(N+E)O(N + E) where NN is number of people and EE is length of dislikes. We visit each node once (outer loop) and traverse every edge twice (once from A to B, once from B to A in adjacency list). Given constraints (N=2000N=2000, E=10000E=10000), this fits well within time limits.
  • Space Complexity: O(N+E)O(N + E) for the adjacency list and color array/queue storage.

Solution

from collections import deque

def possibleBipartition(N: int, dislikes: list[list[int]]) -> bool:
    # Build undirected graph using adjacency list
    adj = [[] for _ in range(N + 1)]
    
    for u, v in dislikes:
        adj[u].append(v)
        adj[v].append(u)

    # Color array to track group assignments. 
    # -1 indicates unvisited/unassigned.
    color = [-1] * (N + 1)
    
    def bfs(start_node):
        queue = deque([start_node])
        color[start_node] = 0
        
        while queue:
            node = queue.popleft()
            
            for neighbor in adj[node]:
                if color[neighbor] == -1: 
                    # Neighbor unvisited, assign opposite group and enqueue
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    # Conflict detected: neighbor already in same group as current node
                    return False
        
        return True

    # Iterate through all people to handle disconnected components
    for i in range(1, N + 1):
        if color[i] == -1:
            if not bfs(i):
                return False
                
    return True

Edge Cases Handled

  • Disconnected Graphs: The outer loop for i in range(1, N + 1) ensures that isolated nodes or separate components are processed individually. If a conflict exists within any component, it is caught immediately during its BFS traversal.
  • Empty Dislikes List: When dislikes is empty, the adjacency list remains empty lists. The loop runs for each node, assigns them arbitrarily (e.g., Group 0), finds no neighbors to check against, and returns True.
  • Single Person (N=1N=1): The range covers index 1 only. No edges exist in adjacency list. BFS completes instantly without conflict checks, returning True.