#2876
Count Visited Nodes in a Directed Graph
international master · 1970 · lc hard +32 · verified · 30.3% accepted · 357 likes · top 7%
Description
A directed graph of n nodes (labeled 0 to n - 1) has exactly n edges. A 0-indexed array edges encodes them: there is an edge from node i to edges[i].
Starting from each node x, follow edges until revisiting a node already visited in this traversal.
Return an array answer where answer[i] is the number of distinct nodes visited when starting from node i.
Example 1:
Input: edges = [1,2,0,0]
Output: [3,3,3,4]
Explanation: We perform the process starting from each node in the following way:
- Starting from node 0, we visit the nodes 0 -> 1 -> 2 -> 0. The number of different nodes we visit is 3.
- Starting from node 1, we visit the nodes 1 -> 2 -> 0 -> 1. The number of different nodes we visit is 3.
- Starting from node 2, we visit the nodes 2 -> 0 -> 1 -> 2. The number of different nodes we visit is 3.
- Starting from node 3, we visit the nodes 3 -> 0 -> 1 -> 2 -> 0. The number of different nodes we visit is 4.
Example 2:
Input: edges = [1,2,3,4,0]
Output: [5,5,5,5,5]
Explanation: Starting from any node we can visit every node in the graph in the process.
Code
1
2
3