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

0% completed

Vote For New Content
Possible Bipartition (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible