Undisputed Top Team

Medium

A tournament has teams teams numbered from 0 to teams - 1. Each record wins[i] = [a, b] means team a is stronger than team b. Strength carries along chains: if a is stronger than b and b is stronger than c, then a is stronger than c. The records never contradict each other, so no team can end up stronger than itself through a chain. A team is a leader if no team is stronger than it. If there is exactly one leader, return its number; otherwise return -1.

Example 1

teams=4, wins=[[2, 0], [0, 3], [2, 1]] → 2

Nobody has beaten team 2, while every other team has lost to someone. So team 2 is the leader.

Example 2

teams=3, wins=[[0, 2]] → -1

Neither team 0 nor team 1 has lost, and they never played each other, so there is no single leader.

Example 3

teams=1, wins=[] → 0

Constraints

1 ≤ teams ≤ 100
0 ≤ len(wins) ≤ teams · (teams - 1) / 2
wins[i] = [a, b], 0 ≤ a, b < teams, a ≠ b
Each pair of teams appears in wins at most once
Chains of wins never form a cycle

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph

Similar problems

Module Build Order Medium Course Enrollment Queue Medium Do the Links Form a Tree Medium Best Roots for a Tree Medium Isolated Groups in a Network Medium

Input

teams=4, wins=[[2, 0], [0, 3], [2, 1]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 66 tests on the server, hidden ones included.