Tournament Rankings
Medium · topological sort
A table-tennis club has n players, numbered 0 to n - 1. Some matches have been played. Each result is a pair [winner, loser] in the list results.
A ranking lists every player exactly once, best first, so that for every result the winner appears somewhere before the loser. A player does not have to have played everyone: a ranking only has to agree with the results you are given.
Return the ranking if exactly one ranking agrees with all the results. If no ranking agrees with them (the results contradict each other), or if more than one does, return an empty list.
The same result may be listed more than once. A player never plays themselves.
Examples
Example 1
Input: n = 3, results = [[2, 0], [0, 1]]
Output: [2, 0, 1]
Player 2 beat 0 and 0 beat 1, so the only ranking is 2, 0, 1.
Example 2
Input: n = 3, results = [[0, 1], [0, 2]]
Output: []
Player 0 is first, but nothing says whether 1 or 2 comes next, so two rankings fit.
Example 3
Input: n = 3, results = [[0, 1], [1, 2], [2, 0]]
Output: []
0 beat 1, 1 beat 2 and 2 beat 0, so nobody can be placed first.
Constraints
- 1 <= n <= 2000
- 0 <= len(results) <= 10000
- Each result holds two different player numbers in the range 0 to n - 1.