边积分最高的节点

难度: Medium

给你一个有向图，图中有 n 个节点，节点编号从 0 到 n - 1 ，其中每个节点都 恰有一条 出边。

图由一个下标从 0 开始、长度为 n 的整数数组 edges 表示，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的有向边。

节点 i 的 边积分 定义为：所有存在一条指向节点 i 的边的节点的编号总和。

返回 边积分 最高的节点。如果多个节点的 边积分 相同，返回编号最小的那个。

示例 1：

输入：edges = [1,0,0,0,0,7,7,5]
输出：7
解释：
- 节点 1、2、3 和 4 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 + 3 + 4 = 10 。
- 节点 0 有一条指向节点 1 的边，节点 1 的边积分等于 0 。
- 节点 7 有一条指向节点 5 的边，节点 5 的边积分等于 7 。
- 节点 5 和 6 都有指向节点 7 的边，节点 7 的边积分等于 5 + 6 = 11 。
节点 7 的边积分最高，所以返回 7 。

示例 2：

输入：edges = [2,0,0,2]
输出：0
解释：
- 节点 1 和 2 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 = 3 。
- 节点 0 和 3 都有指向节点 2 的边，节点 2 的边积分等于 0 + 3 = 3 。
节点 0 和 2 的边积分都是 3 。由于节点 0 的编号更小，返回 0 。

提示：

n == edges.length
2 <= n <= 10⁵
0 <= edges[i] < n
edges[i] != i

Submission

运行时间: 130 ms

内存: 27.3 MB

class Solution:
    def edgeScore(self, edges: List[int]) -> int:
        n = len(edges)
        score = [0] * n
        for i, to in enumerate(edges):
            score[to] += i
        return score.index(max(score))

Explain

题解从每个节点的出边出发，计算所有指向每个节点的边的源节点编号总和，即边积分。使用一个数组score来记录每个节点的边积分，其中score[i]保存了所有指向节点i的源节点编号的总和。遍历一遍edges数组，对于每个节点i，找到它指向的节点to，然后将i累加到score[to]中。最后，使用max函数找出具有最大边积分的节点，并通过index函数获取其索引，即为所求的节点。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def edgeScore(self, edges: List[int]) -> int:
        n = len(edges)  # 总节点数
        score = [0] * n  # 初始化每个节点的边积分为0
        # 遍历每个节点，累加边积分到指向的节点
        for i, to in enumerate(edges):
            score[to] += i
        # 找出边积分最大的节点的索引，即为答案
        return score.index(max(score))

Explore

是的，可能存在一个节点没有任何入边。例如在一个有向图中，若某个节点作为其它节点的出边目标节点时并未出现，则该节点没有任何入边。在题解提供的方法中，这种情况下该节点在score数组中的值会保持为初始化的0。因此，如果没有任何节点指向该节点，其边积分将为0。

题解中使用的数组score的大小是根据节点总数n来初始化的，而节点索引是从0到n-1。由于edges数组中的每个元素都是有效的节点索引，因此在使用score[to]时，to作为edges数组的值，已经保证是一个有效的节点索引，不会超出数组score的索引范围。因此，这种方法考虑了数组索引边界的情况。

Python中的max函数在找到多个最大值的情况下，会返回第一个遇到的最大值。因为score数组是按节点顺序填充的，所以当使用score.index(max(score))时，它会返回具有最大边积分的最小索引节点。因此，题解确实保证了在有多个节点边积分相同的情况下返回编号最小的节点。

在多线程环境下，累加操作不一定是原子操作。例如，在某些编程语言中，如果多个线程同时修改同一个内存位置，则可能导致竞态条件，从而引入数据不一致的问题。然而，题解中的代码是在单线程环境下运行的，因此并发安全问题不适用于此代码。如果在一个多线程环境中执行相同的逻辑，则需要考虑使用锁或其他同步机制来保证操作的原子性。