leetcode在力扣 App 中打开
调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

现有一个有向图,其中包含 n 个节点,节点编号从 0n - 1 。此外,该图还包含了 n 条有向边。

给你一个下标从 0 开始的数组 edges ,其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。

想象在图上发生以下过程:

  • 你从节点 x 开始,通过边访问其他节点,直到你在 此过程 中再次访问到之前已经访问过的节点。

返回数组 answer 作为答案,其中 answer[i] 表示如果从节点 i 开始执行该过程,你可以访问到的不同节点数。

 

示例 1:

输入:edges = [1,2,0,0]
输出:[3,3,3,4]
解释:从每个节点开始执行该过程,记录如下:
- 从节点 0 开始,访问节点 0 -> 1 -> 2 -> 0 。访问的不同节点数是 3 。
- 从节点 1 开始,访问节点 1 -> 2 -> 0 -> 1 。访问的不同节点数是 3 。
- 从节点 2 开始,访问节点 2 -> 0 -> 1 -> 2 。访问的不同节点数是 3 。
- 从节点 3 开始,访问节点 3 -> 0 -> 1 -> 2 -> 0 。访问的不同节点数是 4 。

示例 2:

输入:edges = [1,2,3,4,0]
输出:[5,5,5,5,5]
解释:无论从哪个节点开始,在这个过程中,都可以访问到图中的每一个节点。

 

提示:

  • n == edges.length
  • 2 <= n <= 105
  • 0 <= edges[i] <= n - 1
  • edges[i] != i
通过次数
4K
提交次数
8.6K
通过率
46.7%


相关企业

提示 1
Consider if the graph was only one cycle, what will be the answer for each node?

提示 2
The actual graph will always consist of at least one cycle and some other nodes.

提示 3
Calculate the answer for nodes in cycles the same way as in hint 1. How do you calculate the answer for the remaining nodes?

评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
2 人在线
行 1,列 1
edges =
[1,2,0,0]
Source