#886

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Possible Bipartition

Determine if a group of n people with mutual dislikes can be split into two non-conflicting groups using graph traversal.

depth first search breadth first search union find graph

Problem Statement

You are given n people labeled from 1 to n. Each person may dislike certain others, and the goal is to divide everyone into two groups so that no person is in the same group as someone they dislike.

Given an integer n and an array dislikes where dislikes[i] = [ai, bi] indicates that person ai dislikes person bi, return true if it is possible to split all people into two groups without placing conflicting individuals together. For example, n = 4, dislikes = [[1,2],[1,3],[2,4]] returns true because a valid split exists.

Examples

Example 1

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]

Output: true

The first group has [1,4], and the second group has [2,3].

Example 2

Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]

Output: false

We need at least 3 groups to divide them. We cannot put them in two groups.

Constraints

1 <= n <= 2000
0 <= dislikes.length <= 104
dislikes[i].length == 2
1 <= ai < bi <= n
All the pairs of dislikes are unique.

Solution Approach

Graph Coloring with DFS

Construct a graph where nodes represent people and edges represent dislikes. Use depth-first search to try coloring each node with one of two colors while ensuring adjacent nodes receive opposite colors. If a conflict occurs, return false; otherwise, return true.

Breadth-First Search Variation

Use BFS to traverse the graph iteratively. Start from each unvisited node, assign a color, and enqueue neighbors with the opposite color. Detect conflicts if a neighbor already has the same color. BFS provides similar guarantees as DFS and can handle large graphs efficiently.

Union-Find Method

Treat each dislike pair as a connection that enforces group separation. Use Union-Find to maintain sets of people and merge non-conflicting connections. If any two people who dislike each other end up in the same set, return false. This approach is effective for batch conflict detection and simplifies repeated checks.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(N + E) where N is the number of people and E is the number of dislikes for DFS/BFS, and almost O(E*α(N)) for Union-Find; space is O(N + E) for adjacency lists or O(N) for Union-Find arrays.

What Interviewers Usually Probe

Are you able to model dislikes as a graph and identify conflicts quickly?
Can you implement two-color graph coloring efficiently?
Do you understand both DFS and BFS trade-offs in this context?

Common Pitfalls or Variants

Common pitfalls

Forgetting to check all disconnected components, which may miss a conflict.
Assigning colors incorrectly leading to false positive bipartitions.
Assuming Union-Find alone without proper separation logic guarantees correctness.

Follow-up variants

Allowing more than two groups and checking k-partition feasibility.
Input graph may contain cycles or disconnected subgraphs, testing traversal robustness.
Edge list may be large and require optimized adjacency representation to avoid TLE.

FAQ

What is the main pattern used in Possible Bipartition?

The main pattern is graph traversal with depth-first search or breadth-first search to perform two-color graph coloring.

Can Union-Find solve Possible Bipartition?

Yes, Union-Find can track groups and detect conflicts, ensuring no two people who dislike each other are in the same set.

What should I watch out for when implementing DFS here?

Be careful to visit all disconnected components and maintain correct coloring to avoid false positives.

How does BFS compare to DFS for this problem?

BFS iteratively colors nodes and detects conflicts similarly to DFS but can be easier to manage for large graphs with iterative queues.

What is a common reason Possible Bipartition returns false?

A conflict occurs when two people who dislike each other are forced into the same group, making a two-group split impossible.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        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

        g = defaultdict(list)
        color = [0] * n
        for a, b in dislikes:
            a, b = a - 1, b - 1
            g[a].append(b)
            g[b].append(a)
        return all(c or dfs(i, 1) for i, c in enumerate(color))

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        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

        g = defaultdict(list)
        color = [0] * n
        for a, b in dislikes:
            a, b = a - 1, b - 1
            g[a].append(b)
            g[b].append(a)
        return all(c or dfs(i, 1) for i, c in enumerate(color))

Continue Practicing

#924 minimize malware spread #928 minimize malware spread ii #785 is graph bipartite