LeetCode 题解工作台
有向图访问计数
现有一个有向图，其中包含 n 个节点，节点编号从 0 到 n - 1 。此外，该图还包含了 n 条有向边。 给你一个下标从 0 开始的数组 edges ，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。 想象在图上发生以下过程： 你从节点 x 开始，通过边访问其他节点…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们可以用一个数组 记录每个节点的答案，用一个数组 记录每个节点的访问次序。 遍历每个节点 ，如果当前节点 未被访问，我们就从节点 开始遍历，此时有两种情况：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
现有一个有向图，其中包含 n 个节点，节点编号从 0 到 n - 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.length2 <= n <= 1050 <= edges[i] <= n - 1edges[i] != i
解题思路
方法一：基环树 + 遍历搜索
我们可以用一个数组 记录每个节点的答案，用一个数组 记录每个节点的访问次序。
遍历每个节点 ，如果当前节点 未被访问，我们就从节点 开始遍历，此时有两种情况：
- 如果遍历过程中，遇到了当前节点出发时走过的节点，那么此次遍历，一定是先走到了环内，然后沿着环走了一圈。对于环外的节点，其答案就是环的长度加上节点到环的距离；对于环内的节点，其答案就是环的长度。
- 如果遍历过程中，遇到了此前节点出发时走过的节点，那么对于每个走过的节点，其答案就是当前节点到此节点的距离，加上此节点的答案。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def countVisitedNodes(self, edges: List[int]) -> List[int]:
n = len(edges)
ans = [0] * n
vis = [0] * n
for i in range(n):
if not ans[i]:
cnt, j = 0, i
while not vis[j]:
cnt += 1
vis[j] = cnt
j = edges[j]
cycle, total = 0, cnt + ans[j]
if not ans[j]:
cycle = cnt - vis[j] + 1
total = cnt
j = i
while not ans[j]:
ans[j] = max(total, cycle)
total -= 1
j = edges[j]
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates a strong understanding of dynamic programming techniques, especially state transitions and memoization.
- question_mark
The candidate recognizes the importance of cycle detection and how to handle it efficiently in graph traversal problems.
- question_mark
The candidate's ability to reduce complexity by avoiding redundant computations shows effective problem-solving skills.
常见陷阱
外企场景- error
Failing to handle graph cycles correctly, which could lead to infinite loops during traversal.
- error
Not using memoization, resulting in excessive recalculations and poor performance for large inputs.
- error
Overlooking the edge case where every node is part of a cycle, which could lead to incorrect results.
进阶变体
外企场景- arrow_right_alt
Consider a scenario where the graph is a tree instead of a cycle. How would the solution differ?
- arrow_right_alt
Modify the problem to allow multiple edges between nodes. How would this affect the solution?
- arrow_right_alt
What if the graph has directed edges with weights? How would this impact the dynamic programming approach?