2924. 寻找冠军 II

Medium

题目描述

在一场锦标赛中，有 n 支队伍，编号从 0 到 n - 1；每支队伍也是有向无环图（DAG）中的一个节点。

给你整数 n 和一个长度为 m 的 0索引 二维整数数组 edges 表示这个有向无环图，其中 edges[i] = [ui, vi] 表示图中存在一条从队伍 ui 指向队伍 vi 的有向边。

图中从 a 到 b 的有向边意味着队伍 a 比队伍 b 更强，队伍 b 比队伍 a 更弱。

如果不存在队伍 b 比队伍 a 更强，那么队伍 a 将成为锦标赛的冠军。

如果锦标赛存在唯一冠军，就返回能够成为冠军的队伍。否则，返回 -1。

注意

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

示例 1：

输入：n = 3, edges = [[0,1],[1,2]]
输出：0
解释：队伍 1 比队伍 0 弱。队伍 2 比队伍 1 弱。所以冠军是队伍 0。

示例 2：

输入：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 强。

解题思路

这道题的核心是理解"冠军"的定义：冠军是没有任何队伍比它更强的队伍。

在图论中，这对应于入度为0的节点。因为如果一个队伍有入度（即有其他队伍比它强），那么它就不可能是冠军。

解题思路：

计算入度：遍历所有边，统计每个节点的入度。对于每条边[u, v]，节点v的入度加1。
寻找入度为0的节点：入度为0意味着没有任何队伍比该队伍更强，这样的队伍有资格成为冠军。
判断唯一性：
- 如果恰好有一个入度为0的节点，那么它就是唯一的冠军
- 如果有多个入度为0的节点，说明有多个候选冠军，返回-1
- 如果没有入度为0的节点（在DAG中不可能出现），也返回-1

时间复杂度分析：

遍历所有边计算入度：O(m)
遍历所有节点找入度为0的节点：O(n)
总时间复杂度：O(m + n)

空间复杂度：

需要一个数组存储每个节点的入度：O(n)

代码实现

class Solution {
public:
    int findChampion(int n, vector<vector<int>>& edges) {
        vector<int> inDegree(n, 0);
        
        // 计算每个节点的入度
        for (const auto& edge : edges) {
            inDegree[edge[1]]++;
        }
        
        int champion = -1;
        int count = 0;
        
        // 寻找入度为0的节点
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                champion = i;
                count++;
            }
        }
        
        // 如果恰好有一个入度为0的节点，返回它；否则返回-1
        return count == 1 ? champion : -1;
    }
};

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        in_degree = [0] * n
        
        # 计算每个节点的入度
        for u, v in edges:
            in_degree[v] += 1
        
        champion = -1
        count = 0
        
        # 寻找入度为0的节点
        for i in range(n):
            if in_degree[i] == 0:
                champion = i
                count += 1
        
        # 如果恰好有一个入度为0的节点，返回它；否则返回-1
        return champion if count == 1 else -1

public class Solution {
    public int FindChampion(int n, int[][] edges) {
        int[] inDegree = new int[n];
        
        // 计算每个节点的入度
        foreach (var edge in edges) {
            inDegree[edge[1]]++;
        }
        
        int champion = -1;
        int count = 0;
        
        // 寻找入度为0的节点
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                champion = i;
                count++;
            }
        }
        
        // 如果恰好有一个入度为0的节点，返回它；否则返回-1
        return count == 1 ? champion : -1;
    }
}

var findChampion = function(n, edges) {
    const inDegree = new Array(n).fill(0);
    
    // 计算每个节点的入度
    for (const [u, v] of edges) {
        inDegree[v]++;
    }
    
    let champion = -1;
    let count = 0;
    
    // 寻找入度为0的节点
    for (let i = 0; i < n; i++) {
        if (inDegree[i]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	大小	说明
时间复杂度	O(m + n)	遍历所有边计算入度O(m)，遍历所有节点找冠军O(n)
空间复杂度	O(n)	存储每个节点入度的数组

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析