Forced Sides
A league has n players numbered 0 to n - 1. rivalries is a list of pairs [a, b] with a != b: players a and b refuse to be on the same team; the same pair may appear more than once. The crowd of player x is x together with every player linked to x through a chain of rivalries.
We want to split the crowd of x into two teams so that no two rivals share a team. Return -1 if that is impossible. Otherwise, with y a different player: return 1 if y is in the crowd and every valid split puts x and y on the same team, 2 if y is in the crowd and every valid split puts them on different teams, and 0 if y is not in the crowd of x.
Example 1
Player 1 must be away from 0, and 2 must be away from 1, so 2 ends up with 0.
Example 2
0 and 1 are rivals, so they are always apart.
Example 3
Player 3 has no rivalry at all, so it is not in the crowd of 0.
Constraints
2 <= n <= 500 <= len(rivalries) <= 1000 <= a, b <= n - 1anda != b0 <= x, y <= n - 1andx != y
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Largest PatchMedium
- Longest TrailMedium
- Lowest High PassMedium
- Mutual Reach GroupsMedium
- Nodes on a LoopMedium
- Rectangular IslandsMedium
- Rounds of Parallel JobsMedium
- Sealed RoomsMedium