Smallest Team Split
rivals[i] lists the players that player i refuses to share a team with. Players are numbered 0 to len(rivals) - 1. The lists are symmetric: if j is in rivals[i] then i is in rivals[j]. Nobody is their own rival, and a list may repeat a player.
Split the players into team 1 and team 2 so that no two rivals are on the same team, and return a list team where team[i] is 1 or 2. If several splits work, return the lexicographically smallest list: at the first index where two valid lists differ, pick the one holding 1. Return the empty list [] if no split is possible.
Example 1
Player 1 must be apart from both 0 and 2. Giving player 0 team 1 forces [1, 2, 1], the smallest valid list.
Example 2
Three players who all refuse each other cannot fit into two teams.
Constraints
1 <= len(rivals) <= 500 <= rivals[i][j] < len(rivals)andrivals[i][j] != i- At most 100 entries in total
- The lists are symmetric
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Steps to the ExitMedium
- Through the CheckpointMedium
- Towns Within BudgetMedium
- Break Through WallsHard
- Collect Every KeyHard
- Count the BridgesHard
- Critical JunctionsHard
- Fewest BusesHard