All problems

Two Room Split

Medium · graph traversal

A school trip has n students, numbered 0 to n - 1. The teacher has two classrooms and wants to put every student into exactly one of them. Some pairs of students cannot be trusted together, and are listed in rivals: each entry [a, b] means students a and b must not end up in the same room.

Return true if every student can be placed so that no listed pair shares a room, and false if that is impossible. Either room may end up empty, a student with no rival can go anywhere, and the same pair may be listed more than once.

Examples

Example 1

Input: n = 4, rivals = [[0, 1], [1, 2], [2, 3]]

Output: true

Put students 0 and 2 in one room and students 1 and 3 in the other. Every listed pair is split.

Example 2

Input: n = 3, rivals = [[0, 1], [1, 2], [2, 0]]

Output: false

Whichever rooms 0 and 1 get, student 2 clashes with one of them, so the three can never be split.

Example 3

Input: n = 5, rivals = [[0, 1], [3, 4]]

Output: true

The two pairs do not interact, and student 2 can go anywhere.

Constraints

• 1 <= n <= 5000
• 0 <= len(rivals) <= 20000
• Each entry holds two different student numbers in the range 0 to n - 1.