Possible bipartition

Determine if a set of people can be split into two groups with no mutual dislikes.

bipartite graph bfs dfs coloring

You are given an integer `n` representing the number of people labeled from `1` to `n`, and a list `dislikes` where each element is a list `[a, b]` meaning that person `a` and person `b` dislike each other (mutual). The dislike relation is symmetric and there are no duplicate pairs.

Your task is to implement the function `possible_bipartition(n, dislikes) -> bool` that returns `True` if the people can be divided into two groups such that every pair of people who dislike each other are in different groups, and `False` otherwise.

In other words, the graph with vertices 1..n and edges `dislikes` must be bipartite.

Constraints

1 <= n <= 2000
0 <= len(dislikes) <= 10000
Each pair [a, b] satisfies 1 <= a, b <= n and a != b.
No duplicate pairs; the graph is undirected.

Example

>>> possible_bipartition(4, [[1, 2], [1, 3], [2, 4]])
True

>>> possible_bipartition(3, [[1, 2], [2, 3], [1, 3]])
False

>>> possible_bipartition(5, [[1, 2], [2, 3], [3, 4], [4, 5], [1, 5]])
False

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Build an adjacency list from the dislikes list.

Use BFS or DFS to color the graph with two colors, alternating colors on each edge.

If you ever find an edge connecting two vertices of the same color, the graph is not bipartite.

Isolated vertices (people with no dislikes) can be placed in either group, so ignore them.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.