2924. Find Champion II
Description
There are n
teams numbered from 0
to n - 1
in a tournament; each team is also a node in a DAG.
You are given the integer n
and a 0-indexed 2D integer array edges
of length m
representing the DAG, where edges[i] = [ui, vi]
indicates that there is a directed edge from team ui
to team vi
in the graph.
A directed edge from a
to b
in the graph means that team a
is stronger than team b
and team b
is weaker than team a
.
Team a
will be the champion of the tournament if there is no team b
that is stronger than team a
.
Return the team that will be the champion of the tournament if there is a unique champion, otherwise, return -1
.
Notes
- A cycle is a series of nodes
a1, a2, ..., an, an+1
such that nodea1
is the same node as nodean+1
, the nodesa1, a2, ..., an
are distinct, and there is a directed edge from the nodeai
to nodeai+1
for everyi
in the range[1, n]
. - A DAG is a directed graph that does not have any cycle.
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.
Constraints:
1 <= n <= 100
m == edges.length
0 <= m <= n * (n - 1) / 2
edges[i].length == 2
0 <= edge[i][j] <= n - 1
edges[i][0] != edges[i][1]
- The input is generated such that if team
a
is stronger than teamb
, teamb
is not stronger than teama
. - The input is generated such that if team
a
is stronger than teamb
and teamb
is stronger than teamc
, then teama
is stronger than teamc
.
Solutions
Solution 1: Counting In-degrees
Based on the problem description, we only need to count the in-degrees of each node and record them in an array $indeg$. If only one node has an in-degree of $0$, then this node is the champion; otherwise, there is no unique champion.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes.
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 |