#2924
Find Champion II
pupil · 565 · lc medium +29 · verified · 70.3% accepted · 595 likes · top 79%
Description
In a tournament with n teams (numbered 0 to n - 1), teams are nodes of a DAG. A directed edge [ui, vi] in edges means team ui is stronger than team vi.
A team is champion if no other team is stronger than it.
If there is exactly one champion, return its index. Otherwise return -1.
Notes:
- A DAG is a directed graph that contains no cycles.
- A cycle means a path that leads back to its starting node.
Example 1:
Input: n = 3, edges = [[0,1],[1,2]]
Output: 0
Explanation: Team 1 is weaker than team 0. Team 2 is weaker than team 1. So the champion is team 0.
Example 2:
Input: n = 4, edges = [[0,2],[1,3],[1,2]]
Output: -1
Explanation: Team 2 is weaker than team 0 and team 1. Team 3 is weaker than team 1. But team 1 and team 0 are not weaker than any other teams. So the answer is -1.
Code
1
2
3