All problems

Possible Bipartition

Medium · graph traversal

A school has n pupils, numbered 1 to n, and a teacher wants to split them into two teams for a sports day. You are given the list dislikes. Each entry [a, b] means pupil a and pupil b cannot stand each other, so they must not be on the same team. The dislike goes both ways.

Every pupil joins exactly one of the two teams, and a team may end up empty. Pupils who appear in no entry can go on either team.

Return true if a split exists that keeps every disliking pair on different teams, and false otherwise.

No pupil dislikes themselves, and no pair is listed twice (in either order).

Examples

Example 1

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

Output: true

Put pupils 1 and 4 on one team, and pupils 2 and 3 on the other.

Example 2

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

Output: false

All three pupils dislike each other, so with only two teams two of them must be together.

Example 3

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

Output: true

Alternate along the chain: pupils 1, 3 and 5 on one team, and 2 and 4 on the other.

Constraints

• 1 <= n <= 2000
• 0 <= len(dislikes) <= 10^4
• Each entry holds two different pupil numbers in the range 1 to n.
• No pair appears more than once, in either order.