[Google Virtual Interview] Determine Precise Player Rankings - Graph Theory Problem

Problem Description

In a chess tournament with N players, each player has a distinct rank from 1 to N (where rank 1 is the best player and rank N is the worst). In any game between two players, the higher-ranked player (lower rank number) always wins.

Given the results of M games in the format [winner, loser], determine which players' ranks can be precisely determined.

A player's rank can be precisely determined if we can establish their exact position in the ranking through the transitive relationships from all game results.

Function Signature

vector<pair<int, int>> determineRanks(vector<vector<int>>& games, int n);

Parameters:

• games: A 2D array where games[i] = [winner, loser] represents that player winner beat player loser
• n: The total number of players (numbered from 1 to n)

Returns:

• A vector of pairs [player, rank] for players whose ranks can be precisely determined

Examples

Example 1:

Input: games = [[4,3],[4,2],[3,2],[1,2],[2,5]], n = 5
Output: [[2,4],[5,5]]

Explanation:
- Player 2 lost to players 1, 3, 4 and won against player 5
- Since we know 3 players beat player 2 and player 2 beats 1 player,
  player 2's rank is precisely 4 (3 + 1 = 4)
- Player 5 lost to player 2, and we know player 2 lost to 3 other players
- So player 5 is beaten by all other players, making their rank precisely 5

Example 2:

Input: games = [[1,2],[2,3],[3,4],[3,5],[4,6],[5,6]], n = 6
Output: [[1,1],[2,2],[3,3],[6,6]]

Explanation:
- Player 1: beats everyone transitively (2,3,4,5,6), beaten by none → rank 1
- Player 2: beats (3,4,5,6), beaten by (1) → rank 2
- Player 3: beats (4,5,6), beaten by (1,2) → rank 3
- Player 6: beats none, beaten by everyone (1,2,3,4,5) → rank 6
- Players 4,5: both beat only (6) and beaten by (1,2,3), so 3+1+1=5≠6
  They could be rank 4 or 5, cannot be precisely determined

Constraints

• 1 <= n <= 1000
• 0 <= games.length <= min(n*(n-1)/2, 2000)
• games[i].length == 2
• 1 <= games[i][0], games[i][1] <= n
• games[i][0] != games[i][1]
• No duplicate games
• All game results are consistent with some valid ranking