FunctionRacerProblemsRace

Forced Sides

MediumGraphsPython, JavaScript, TypeScript, Java, C++

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

n 4
rivalries [[0,1],[1,2]]
x 0
y 2
returns 1

Player 1 must be away from 0, and 2 must be away from 1, so 2 ends up with 0.

Example 2

n 4
rivalries [[0,1],[1,2]]
x 0
y 1
returns 2

0 and 1 are rivals, so they are always apart.

Example 3

n 4
rivalries [[0,1],[1,2]]
x 0
y 3
returns 0

Player 3 has no rivalry at all, so it is not in the crowd of 0.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems