Watch 10 video solutions for Possible Bipartition, a medium level problem involving Depth-First Search, Breadth-First Search, Union Find. This walkthrough by Techdose has 54,083 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
We want to split a group of n people (labeled from 1 to n) 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] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.
Example 1:
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]] Output: true Explanation: 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 Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.
Constraints:
1 <= n <= 20000 <= dislikes.length <= 104dislikes[i].length == 21 <= ai < bi <= ndislikes are unique.