2876：有向图访问计数（2209 分）

Ian

2023-10-01 约 615 字预计阅读 2 分钟次阅读

力扣第 365 场周赛第 4 题

题目

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

分析

2360 升级版

先拓扑排序去掉树枝
遍历剩下的环，每个节点的答案即是环长
再递归得到树枝节点的答案即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution:
    def countVisitedNodes(self, edges: List[int]) -> List[int]:
        n = len(edges)
        ind = [0]*n
        for u in edges:
            ind[u]+=1
        Q = deque(u for u in range(n) if ind[u]==0)
        while Q:
            u = Q.popleft()
            v = edges[u]
            ind[v] -= 1
            if ind[v]==0:
                Q.append(v)
        res = [0]*n
        for u in range(n):
            if ind[u]:
                w = 0
                while ind[u]:
                    ind[u] = 0
                    u = edges[u]
                    w += 1
                for _ in range(w):
                    res[u] = w
                    u = edges[u]
        def dfs(u):
            res[u] = res[u] or dfs(edges[u])+1
            return res[u]
        for u in range(n):
            dfs(u)
        return res

392 ms

目录

2876：有向图访问计数（2209 分）

题目

分析

解答