MediumDepth-First SearchBreadth-First SearchUnion FindGraph

Possible Bipartition

1 approach, code in every language

There are n people numbered from 1 to n. Some pairs of people dislike each other, given as a list dislikes where dislikes[i] = [ai, bi] means person ai and person bi refuse to be in the same group.

You want to divide everyone into exactly two groups of any size such that no pair of people who dislike each other end up in the same group.

Return true if such a division is possible, and false otherwise.

Example 1

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

Output: true

Group 1 = {1, 4} and Group 2 = {2, 3} satisfies every dislike: 1 is apart from 2 and 3, and 2 is apart from 4.

Example 2

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

Output: false

The three people mutually dislike each other, forming a triangle. Two groups cannot separate three pairwise-conflicting people.

Constraints

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

Dislike Graph 2-Coloring

Model each dislike as an edge, then attempt to 2-color the graph; a same-color dislike edge means partitioning is impossible.

Loading animation…

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

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

Time

O(n + E)

Space

O(n + E)

E is the number of dislike pairs; building and traversing the adjacency list is linear in nodes plus edges.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Kennel Split Into Two Yards is our own problem on the technique behind Possible Bipartition: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free