Loading
Loading
A five-a-side league is splitting its players into two training squads. Some pairs of players are rivals and must not share a squad. Players with no rivalries can go anywhere.
rivals[i] lists every rival of player i; rivalry is mutual, so if j appears in rivals[i] then i appears in rivals[j]. Return true if the players can be divided into two squads with no rivals together.
rivals = [[1,3],[0,2],[1,3],[0,2]]0 → Astart with player 01, 3 → Brivals of 0 go to the other squad2 → Arival of 1 and 3, and nobody in A is its rivalsquads {0,2} {1,3}every rivalry crosses the splittrueSign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
| 0 | 1 | 3 |
|---|---|---|
| 1 | 0 | 2 |
| 2 | 1 | 3 |
| 3 | 2 | 0 |
Example 2
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(n + rivalries) time · O(n) space
Input. Run your code to watch it work on this input, one line at a time.
| 0 | 1 | 3 |
|---|---|---|
| 1 | 0 | 2 |
| 2 | 1 | 3 |
| 3 | 2 | 0 |
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
| 0 | 1 | 2 |
|---|---|---|
| 1 | 0 | 2 |
| 2 | 1 | 0 |
Players 0, 1 and 2 are mutual rivals; two teams cannot separate all three.
Example 3
| 0 | 1 |
|---|---|
| 1 | 0 |
| 2 | 3 |
| 3 | 2 |
| 4 |