Split Into Two Squads

MediumGraphs

Problem

A coach has n players numbered 0 to n - 1. Each entry [a, b] of rivalries says players a and b refuse to be on the same squad.

Return true if the players can be split into two squads (either may be empty) so that no two rivals share a squad, and false otherwise.

Example 1

Input:
n = 4, rivalries = [[0, 1], [1, 2], [2, 3], [3, 0]]
Output:
true

Squads {0, 2} and {1, 3}.

Example 2

Input:
n = 3, rivalries = [[0, 1], [1, 2], [2, 0]]
Output:
false

In a triangle of rivals, two of the three always end up together.

Example 3

Input:
n = 5, rivalries = [[0, 1], [2, 3]]
Output:
true

Constraints

  • 1 ≤ n ≤ 10^4
  • 0 ≤ rivalries.length ≤ 2·10^4
  • 0 ≤ a, b < n, a ≠ b

Hint

Show the first hint

Pick any player and put them on squad A. Where must each of their rivals go?

Walkthrough

How to approach it

01Clarify before coding

  • Can a squad be empty? Yes, so players with no rivals never cause trouble.
  • Is the graph connected? Not necessarily; each component must be checked.
  • Can a rivalry repeat? Yes, it changes nothing.

02Brute force

Try all 2^n assignments of players to squads and test every rivalry.

Cost: O(2^n · m): impossible past n ≈ 25.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.