找到冠军 II

标签: 图

难度: 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：

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

Submission

运行时间: 51 ms

内存: 17.0 MB

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        champion = list(range(n))
        for i in edges:
            champion[i[1]] = -1
        ans = []
        for i in champion:
            if i > -1:
                ans.append(i)
        return ans[0] if len(ans) == 1 else -1

Explain

题解通过维护一个包含所有队伍的列表来标记可能的冠军队伍。遍历给定的边，对于每一条边 [u, v]，标记 v 队因为存在比它强的 u 队而不可能是冠军，通过将 champion[v] 设为 -1 实现。最后，所有未被标记为 -1 的队伍即是没有比它强的队伍的候选者。如果存在唯一的候选者，则这个候选者是冠军；如果不存在或存在多个，则返回 -1。

时间复杂度: O(n + m)

空间复杂度: O(n)

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        # 初始化一个列表，包含所有队伍
        champion = list(range(n))
        # 标记每个非冠军队伍，即存在强队的队伍
        for i in edges:
            champion[i[1]] = -1
        # 筛选可能的冠军队伍
        ans = []
        for i in champion:
            if i > -1:
                ans.append(i)
        # 判断是否有唯一冠军
        return ans[0] if len(ans) == 1 else -1

Explore

题解中的算法没有直接考虑孤立节点的情况。因为算法是通过遍历边来标记非冠军队伍的，所以任何未在边中出现的节点都不会被标记为-1。如果一个节点即没有入边也没有出边，它将不会被任何边的遍历影响，从而保留在可能的冠军列表中。这意味着孤立节点仍然被视为可能的冠军候选，除非存在其他未被标记的节点。

题解中对champion数组的更新方式保证了边的输入顺序不会影响最终的结果。由于每个边的遍历都是将目标节点（即边的第二个元素）标记为-1，这个操作是幂等的，即多次对同一节点进行此操作与进行一次操作的结果相同。因此，不论边的输入顺序如何，最后被标记为-1的节点集合都将是相同的，从而保证了结果的一致性。

如果所有的边都是从一个或多个节点指向同一个节点，那么这个目标节点将被标记为-1，因为它有入边表示存在比它强的队伍。其他所有未被标记的节点都没有入边，这意味着没有其他节点比它们强，因此这些未被标记的节点都是冠军的候选。如果除了被指向的节点外只有一个未被标记的节点，则该节点是冠军。如果有多个这样的节点，解决方案无法确定唯一的冠军，将返回-1。

当前题解的算法设计中并没有区分'没有冠军'与'存在多个冠军'的情况。在实际应用中，如果需要明确区分这两种情况，可以引入额外的逻辑。例如，可以计算结果列表ans的长度，如果长度为0，则没有冠军；如果长度大于1，则存在多个冠军。这样可以通过长度来明确返回的-1是由于哪种情况引起的，从而提供更详细的信息。