【2024.04.13】LeetCode每日一题·找到冠军 II

2024年04月14日 0时27分

标签： LeetCode 图 Medium

## 题目描述

一场比赛中共有`n`支队伍，按从`0`到`n - 1`编号。每支队伍也是**有向无环图（DAG）**上的一个节点。

给你一个整数`n`和一个下标从`0`开始、长度为`m`的二维整数数组`edges`表示这个有向无环图，其中`edges[i] = [ui, vi]`表示图中存在一条从`ui`队到`vi`队的有向边。

从`a`队到`b`队的有向边意味着`a`队比`b`队**强**，也就是`b`队比`a`队**弱**。

在这场比赛中，如果不存在某支强于`a`队的队伍，则认为`a`队将会是**冠军**。

如果这场比赛存在**唯一**一个冠军，则返回将会成为冠军的队伍。否则，返回 `-1`。

注意

* **环**是形如`a1, a2, ..., an, an+1`的一个序列，且满足：节点`a1`与节点`an+1`是同一个节点；节点`a1, a2, ..., an`互不相同；对于范围`[1, n]`中的每个`i`，均存在一条从节点`ai`到节点`ai+1`的有向边。
* 有向无环图 是不存在任何环的有向图。

#### 示例1
![](https://assets.leetcode.com/uploads/2023/10/19/graph-3.png)
````
输入：n = 3, edges = [[0,1],[1,2]]
输出：0
解释：1 队比 0 队弱。2 队比 1 队弱。所以冠军是 0 队。
````

#### 示例2
![](https://assets.leetcode.com/uploads/2023/10/19/graph-4.png)
````
输入：n = 4, edges = [[0,2],[1,3],[1,2]]
输出：-1
解释：2 队比 0 队和 1 队弱。3 队比 1 队弱。但是 1 队和 0 队之间不存在强弱对比。所以答案是 -1 。
````

#### 提示
````
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]
生成的输入满足：如果 a 队比 b 队强，就不存在 b 队比 a 队强
生成的输入满足：如果 a 队比 b 队强，b 队比 c 队强，那么 a 队比 c 队强
````

#### 来源

> 来源：力扣（LeetCode）
> 
> 链接：[2924. 找到冠军 II](https://leetcode.cn/problems/find-champion-ii/description/)

## 解题思路
最强的队伍其**入度**应该为`0`，统计这样的节点是否存在多个即可。

时间复杂度：$$O(n + m)$$ （$$n$$为节点数，$$M$$为边数）

## 代码
````cpp
class Solution {
public:
    int findChampion(int n, vector<vector<int>>& edges) {
        vector<int> d(n, 0);
        int res = -2;
        for(auto& e: edges){
            d[e[1]]++;
        }
        for(int i = 0; i < n; i++){
            if(d[i] == 0){
                if(res == -2)
                    res = i;
                else{
                    res = -1;
                    break;
                }
            }
        }
        return res;
    }
};
````

### 用时和内存
> 执行用时：167 ms，在所有C++提交中击败了64.83%的用户
>
> 内存消耗：90.36 MB，在所有C++提交中击败68.68%的用户
>

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【2024.04.13】LeetCode每日一题·找到冠军 II

所有评论

暂无评论

新增评论