Problem Breakdown
We are given 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 ().dislikes: List of pairs indicating a conflict between person and person .
- Outputs: Boolean (
Trueif bipartition is possible,Falseotherwise). - 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
dislikeslist implies everyone can go into any group, so it should returnTrue. - 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 ( possibilities). For , 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
- Graph Construction: Convert
dislikesinto an adjacency list representation since and edge count are manageable ( space), making traversal efficient. Note that dislikes imply a bidirectional relationship: if A dislikes B, B dislikes A. - State Tracking: Initialize a
colorarray of size with -1 (representing unvisited). We use indices 0 and 1 to represent the two groups. - Traversal Loop: Iterate through every person from to . 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.
- 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_colorand enqueue. - If neighbor is already assigned, verify its color differs from current node’s color (
color[neighbor] != color[node]).
- Conflict Detection: If we find a visited neighbor with the same group assignment as the current node, return
Falseimmediately (odd cycle detected). - Completion: If all components are traversed without conflict, return
True.
Complexity Analysis
- Time Complexity: where is number of people and 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 (, ), this fits well within time limits. - Space Complexity: 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
dislikesis 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 returnsTrue. - Single Person (): The range covers index 1 only. No edges exist in adjacency list. BFS completes instantly without conflict checks, returning
True.