有向图访问计数

标签: 图 记忆化搜索 动态规划

难度: Hard

现有一个有向图，其中包含 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.length
  • 2 <= n <= 105
  • 0 <= edges[i] <= n - 1
  • edges[i] != i

Submission

运行时间: 249 ms

内存: 92.6 MB

class Solution:
    def countVisitedNodes(self, edges: List[int]) -> List[int]:
        n = len(edges)
        ans = [0] * n
        depth = [0] * n
        
        def fixRing(curNode: int, ringLength: int):
            while ans[curNode] == 0:
                ans[curNode] = ringLength
                curNode = edges[curNode]

        def dfs(curNode: int, curDepth: int):
            depth[curNode] = curDepth
            nextNode = edges[curNode]
            if ans[nextNode] > 0: ans[curNode] = ans[nextNode] + 1
            elif depth[nextNode] > 0: fixRing(curNode, curDepth - depth[nextNode] + 1)
            else:
                dfs(nextNode, curDepth + 1)
                if ans[curNode] == 0: ans[curNode] = ans[nextNode] + 1

        for cur in range(n):
            if ans[cur] == 0: dfs(cur, 1)

        return ans

Explain

该题解使用了深度优先搜索（DFS）来探索图，并借助额外的数组来存储每个节点开始的遍历信息。从每个节点开始，使用DFS遍历直到遇到已访问的节点，从而检测出环。\n\n1. 使用`ans`数组存储每个节点开始的遍历可以访问的不同节点数。\n2. 使用`depth`数组记录每个节点在当前DFS路径的深度。\n3. `fixRing`函数用于更新在环中的所有节点的访问节点数。\n4. `dfs`函数用于深度优先搜索，它检查下一个节点是否已被解决（即`ans[nextNode] > 0`），或者是否已在当前路径上访问过以形成环（即`depth[nextNode] > 0`）。根据情况，更新当前节点的访问节点数或调用`fixRing`函数。\n5. 主循环确保从每个尚未解决的节点开始DFS。\n\n通过这种方式，每个节点的访问计数被逐步建立，直到图中所有节点的访问计数都被确定。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def countVisitedNodes(self, edges: List[int]) -> List[int]:
        n = len(edges)
        ans = [0] * n  # 存储每个节点的访问节点数
        depth = [0] * n  # 存储节点在DFS中的深度
        
        def fixRing(curNode: int, ringLength: int):
            # 更新环中每个节点的访问节点数
            while ans[curNode] == 0:
                ans[curNode] = ringLength
                curNode = edges[curNode]
        
        def dfs(curNode: int, curDepth: int):
            depth[curNode] = curDepth
            nextNode = edges[curNode]
            if ans[nextNode] > 0: ans[curNode] = ans[nextNode] + 1
            elif depth[nextNode] > 0: fixRing(curNode, curDepth - depth[nextNode] + 1)
            else:
                dfs(nextNode, curDepth + 1)
                if ans[curNode] == 0: ans[curNode] = ans[nextNode] + 1
        
        for cur in range(n):
            if ans[cur] == 0: dfs(cur, 1)
        
        return ans

Explore

在`dfs`函数中，当遇到一个节点`nextNode`已经被访问过（即`ans[nextNode] > 0`），说明从`nextNode`开始的所有可能的访问节点数已经被确定。因此，当前节点`curNode`的访问节点数应等于`nextNode`的访问节点数加上`nextNode`本身，即`ans[curNode] = ans[nextNode] + 1`。这种方式确保了每个节点的访问计数只被计算一次，避免了重复计数。同时，由于每个节点只在其访问计数未被解决时进行深度优先搜索，这避免了错过某些节点的计数。

`depth`数组记录每个节点在当前DFS路径中的深度。当在DFS过程中遇到一个已在当前DFS路径上的节点`nextNode`（即`depth[nextNode] > 0`时），意味着从当前节点到`nextNode`形成了一个环。环的长度可以通过当前节点的深度`curDepth`减去`nextNode`的深度`depth[nextNode]`再加1得到，即`curDepth - depth[nextNode] + 1`。这个长度直接用于修正环中每个节点的访问节点数。

`fixRing`函数在更新环中每个节点的访问节点数时，只会处理那些`ans`值为0的节点，即那些尚未解决访问计数的节点。函数从当前节点开始，沿着`edges`数组指示的方向遍历，直到遇到一个其`ans`值已非0的节点，此时停止更新。这样保证了只更新环中的节点。由于环外的节点在这个过程中`ans`值不是0，所以不会被错误地更新。

该算法即使在存在多个环或环交叉的复杂情况下也是有效的。算法通过从每个节点开始的独立DFS确保每个节点的访问计数能够被正确计算。对于每个起始节点，DFS搜索会记录路径并通过`depth`数组检测和处理环。即使环相交或多个环存在，每次遇到环的处理（通过`fixRing`函数）确保了在该环中每个节点的访问计数都能正确更新，而不受其他环的影响。因此，无论环的结构如何复杂，每个节点的访问计数都会在其对应的DFS中被正确解决。