Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Possible Bipartition (medium)
On this page

Problem Statement

Examples

Try it yourself

Problem Statement

There are n people (labeled from 1 to n), and need to split them into two groups of any size. Each person may dislike some other people, and they should not go into the same group.

Given the integer n and the array dislikes where dislikes[i] = [a<sub>i</sub>, b<sub>i</sub>] indicates that the person labeled a<sub>I</sub> does not like the person labeled b<sub>I</sub>, return true if you can divide each person into two groups in this way. Otherwise, return false.

Examples

Example 1

  • Input: n = 5, dislikes = [[1, 2], [2, 3], [3, 4], [4, 5]]
  • Expected Output: true
  • Justification: We can split the group into two sets: {1, 3, 5} and {2, 4}. Each person in one group dislikes only those in the other group.

Example 2

  • Input: n = 6, dislikes = [[1, 2], [2, 4], [4, 6],[4, 5], [5, 6]]
  • Expected Output: false
  • Justification: It's impossible to split all persons in 2 parts.

Example 3

  • Input: n = 3, dislikes = [[1, 2], [1, 3]]
  • Expected Output: true
  • Justification: We can split the group into two sets: {1} and {2, 3}. Each person in one group dislikes only those in the other group.

Constraints:

  • 1 <= n <= 2000
  • 0 <= dislikes.length <= 10<sup>4</sup>
  • dislikes[i].length == 2
  • 1 <= a<sub>i</sub> < b<sub>i</sub> <= n
  • All the pairs of dislikes are unique.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Examples

Try it yourself