Problem Description

You have n people labeled from 1 to n that need to be divided into exactly two groups. Some people dislike each other and cannot be placed in the same group.

You're given:

• An integer n representing the number of people
• An array dislikes where each element dislikes[i] = [aᵢ, bᵢ] means person aᵢ dislikes person bᵢ (and vice versa)

Your task is to determine if it's possible to split all n people into two groups such that no two people who dislike each other are in the same group. Return true if such a division is possible, false otherwise.

The problem is essentially asking whether you can create a valid bipartition of people based on their dislike relationships. This is equivalent to checking if the graph formed by the dislike relationships is bipartite - meaning the graph can be colored with two colors such that no two adjacent nodes (people who dislike each other) have the same color.

The solution uses depth-first search (DFS) with graph coloring. It builds an adjacency list from the dislikes array, then attempts to color each connected component with alternating colors (represented as 1 and 2). If at any point two people who dislike each other would need the same color, the bipartition is impossible. The code converts 1-indexed people to 0-indexed for easier array manipulation and uses 3 - c to alternate between colors 1 and 2.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves people (nodes) and their dislike relationships (edges). We need to model this as a graph where each person is a node and each dislike relationship creates an edge between two nodes.

Is it a tree?

• No: The graph is not necessarily a tree. It can have cycles (e.g., person A dislikes B, B dislikes C, and C dislikes A), and it may have multiple disconnected components.

Is the problem related to directed acyclic graphs?

• No: The dislike relationships are bidirectional (if A dislikes B, then B dislikes A), making this an undirected graph. Also, the graph may contain cycles.

Is the problem related to shortest paths?

• No: We're not trying to find the shortest path between nodes. Instead, we need to determine if we can partition the nodes into two groups.

Does the problem involve connectivity?

• Yes: The problem involves checking if we can properly color/partition the graph. This is essentially a bipartite graph detection problem, which requires exploring the connectivity and relationships between nodes.

Does the problem have small constraints?

• Yes: With constraints typically up to n = 2000 and a limited number of dislikes, we can use DFS to explore each connected component.

DFS/backtracking?

• Yes: DFS is perfect for this problem. We can use DFS to traverse each connected component and attempt to color nodes with alternating colors (representing the two groups).

Conclusion: The flowchart suggests using DFS to solve this bipartite graph detection problem. We traverse the graph using DFS, assigning alternating colors to connected nodes, and check if any conflicts arise (two connected nodes having the same color).

Intuition

The key insight is recognizing that this is a graph bipartition problem. If we think of people as nodes and dislikes as edges, we need to color the graph with exactly two colors such that no adjacent nodes share the same color.

Why does this work? Consider what happens when we try to split people into two groups:

• Each person must go into one of two groups (let's call them Group 1 and Group 2)
• If person A dislikes person B, they must be in different groups
• This is exactly like coloring a graph with two colors where adjacent nodes must have different colors

The critical realization is that a graph can be 2-colored (bipartite) if and only if it contains no odd-length cycles. Why? In any cycle, if we alternate colors around it, an odd-length cycle would force us to give the same color to two adjacent nodes, creating a conflict.

Our approach uses DFS to traverse each connected component:

1. Start with any uncolored person and assign them to Group 1 (color 1)
2. All their disliked people must go to Group 2 (color 2)
3. All people disliked by Group 2 members must go back to Group 1
4. Continue this alternating pattern

If at any point we try to assign a color to someone who already has a different color assigned, we've found a conflict - the graph isn't bipartite, and we can't split the people into two valid groups.

The beauty of this solution is that DFS naturally handles disconnected components. Some people might not dislike anyone or be disliked by anyone - they form separate components that we can color independently. The all(c or dfs(i, 1) for i, c in enumerate(color)) ensures we check every component, starting a new DFS whenever we find an uncolored node.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.

Solution Approach

The implementation uses DFS with graph coloring to detect if the graph formed by dislike relationships is bipartite.

Data Structures:

• g: An adjacency list (using defaultdict(list)) to represent the undirected graph of dislikes
• color: An array where color[i] stores the color (group) of person i (0 = uncolored, 1 = Group 1, 2 = Group 2)

Building the Graph:

for a, b in dislikes:
    a, b = a - 1, b - 1  # Convert to 0-indexed
    g[a].append(b)
    g[b].append(a)

Since dislikes are mutual, we add edges in both directions to create an undirected graph.

DFS Coloring Function:

def dfs(i, c):
    color[i] = c
    for j in g[i]:
        if color[j] == c:
            return False
        if color[j] == 0 and not dfs(j, 3 - c):
            return False
    return True

The DFS function attempts to color person i with color c:

1. Assign color c to person i
2. For each person j that person i dislikes:
   • If j already has the same color c, we have a conflict → return False
   • If j is uncolored (0), recursively color it with the opposite color 3 - c (alternates between 1 and 2)
   • If the recursive coloring fails, propagate the failure

Main Logic:

return all(c or dfs(i, 1) for i, c in enumerate(color))

This line handles multiple disconnected components:

• For each person i, check if they're already colored (c is non-zero)
• If uncolored, start a new DFS from that person with color 1
• The expression c or dfs(i, 1) returns True if either:
  • Person is already colored (part of a previously processed component)
  • Starting a new DFS from this person succeeds
• Using all() ensures every component can be properly 2-colored

Time Complexity: O(V + E) where V is the number of people and E is the number of dislike relationships Space Complexity: O(V + E) for the adjacency list and color array

Example Walkthrough

Let's walk through a small example with n = 5 people and dislikes = [[1,2], [2,3], [3,4], [4,5], [1,5]].

Step 1: Build the graph After converting to 0-indexed and creating the adjacency list:

• Person 0 dislikes: [1, 4]
• Person 1 dislikes: [0, 2]
• Person 2 dislikes: [1, 3]
• Person 3 dislikes: [2, 4]
• Person 4 dislikes: [3, 0]

Step 2: Initialize color array color = [0, 0, 0, 0, 0] (all uncolored)

Step 3: Start DFS from person 0

• Color person 0 with color 1: color = [1, 0, 0, 0, 0]
• Person 0 dislikes persons 1 and 4, so we need to color them with 2

Step 4: DFS to person 1

• Color person 1 with color 2: color = [1, 2, 0, 0, 0]
• Person 1 dislikes person 0 (already colored 1, different from 2 ✓) and person 2
• DFS to person 2 with color 1

Step 5: DFS to person 2

• Color person 2 with color 1: color = [1, 2, 1, 0, 0]
• Person 2 dislikes person 1 (already colored 2, different from 1 ✓) and person 3
• DFS to person 3 with color 2

Step 6: DFS to person 3

• Color person 3 with color 2: color = [1, 2, 1, 2, 0]
• Person 3 dislikes person 2 (already colored 1, different from 2 ✓) and person 4
• DFS to person 4 with color 1

Step 7: DFS to person 4

• Color person 4 with color 1: color = [1, 2, 1, 2, 1]
• Person 4 dislikes person 3 (already colored 2, different from 1 ✓) and person 0
• Check person 0: it has color 1, same as person 4's color 1 ✗

Conflict detected! Person 4 and person 0 dislike each other but would need the same color. This forms an odd cycle (0→1→2→3→4→0) of length 5, making bipartition impossible.

The function returns False - we cannot split these 5 people into two groups.

Counter-example that works: If we had dislikes = [[1,2], [2,3], [3,4]] with n = 4:

• DFS colors: person 0 (color 1), person 1 (color 2), person 2 (color 1), person 3 (color 2)
• Final groups: Group 1 = {1, 3}, Group 2 = {2, 4}
• No conflicts, returns True

Solution Implementation

Time and Space Complexity

Time Complexity: O(V + E) where V = n is the number of people and E is the number of dislike relationships.

• Building the adjacency list takes O(E) time as we iterate through all dislike pairs once
• The DFS traversal visits each vertex at most once and explores each edge at most twice (once from each endpoint)
• For each vertex, we process all its adjacent vertices, which in total across all vertices is O(E)
• The all() function with the generator expression triggers DFS for each unvisited component, but the total work done across all DFS calls is still bounded by O(V + E)

Space Complexity: O(V + E)

• The adjacency list g stores all edges, requiring O(E) space (each edge is stored twice in an undirected graph)
• The color array uses O(V) space to track the coloring of each vertex
• The recursive DFS call stack can go as deep as O(V) in the worst case (when the graph forms a long path)
• Total space complexity is O(V + E)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Convert Between 1-indexed and 0-indexed

One of the most common mistakes is forgetting that the problem uses 1-indexed people (labeled from 1 to n) while arrays in most programming languages are 0-indexed.

Incorrect approach:

# Forgetting to convert indices
for person_a, person_b in dislikes:
    adjacency_list[person_a].append(person_b)  # Wrong! Using 1-indexed directly
    adjacency_list[person_b].append(person_a)
  
colors = [0] * n
# Later accessing colors[person_a] where person_a could be n, causing IndexError

Solution: Always convert to 0-indexed immediately when processing the input:

for person_a, person_b in dislikes:
    person_a -= 1  # Convert to 0-indexed
    person_b -= 1
    adjacency_list[person_a].append(person_b)
    adjacency_list[person_b].append(person_a)

2. Not Handling Disconnected Components

Another critical mistake is assuming all people form a single connected graph. If there are isolated groups of people with no dislikes between groups, you need to check each component separately.

Incorrect approach:

# Only checking from node 0
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
    # ... build graph ...
    if not dislikes:
        return True
    return dfs(0, 1)  # Wrong! Only checks component containing person 0

Solution: Iterate through all nodes and start a new DFS for each uncolored node:

# Check all nodes, starting new DFS for uncolored ones
return all(color != 0 or dfs(node_idx, 1) 
           for node_idx, color in enumerate(colors))

3. Using Wrong Color Alternation Logic

When alternating between two colors/groups, using incorrect logic can lead to assigning the same color to adjacent nodes.

Incorrect approaches:

# Wrong: This doesn't alternate properly
dfs(neighbor, assigned_color + 1)  # Could give color 3, 4, etc.

# Wrong: Using modulo incorrectly
dfs(neighbor, assigned_color % 2)  # Color 1 → 1, Color 2 → 0 (invalid)

Solution: Use 3 - assigned_color to alternate between colors 1 and 2:

dfs(neighbor, 3 - assigned_color)  # Color 1 → 2, Color 2 → 1

4. Not Checking Already Colored Nodes Properly

Failing to handle the case where a neighbor is already colored (but with a valid different color) can cause unnecessary recursion or incorrect results.

Incorrect approach:

def dfs(node, assigned_color):
    colors[node] = assigned_color
    for neighbor in adjacency_list[node]:
        if colors[neighbor] == assigned_color:
            return False
        # Wrong: Recursing even when neighbor is already correctly colored
        if not dfs(neighbor, 3 - assigned_color):  
            return False
    return True

Solution: Only recurse on uncolored neighbors:

def dfs(node, assigned_color):
    colors[node] = assigned_color
    for neighbor in adjacency_list[node]:
        if colors[neighbor] == assigned_color:
            return False
        # Only recurse if neighbor is uncolored
        if colors[neighbor] == 0 and not dfs(neighbor, 3 - assigned_color):
            return False
    return True