Count Visited Nodes in a Directed Graph
There is a directed graph consisting of n nodes numbered from 0 to n - 1 and n directed edges.
You are given a 0-indexed array edges where edges[i] indicates that there is an edge from node i to node edges[i].
Consider the following process on the graph:
- You start from a node
xand keep visiting other nodes through edges until you reach a node that you have already visited before on this same process.
Return an array answer where answer[i] is the number of different nodes that you will visit if you perform the process starting from node i.
Example 1
Input
edges = [1,2,0,0]Output
[3,3,3,4]Starting from nodes 0, 1, and 2 visits the 3-node cycle, while starting from node 3 visits node 3 plus that cycle for 4 different nodes.
Example 2
Input
edges = [1,2,3,4,0]Output
[5,5,5,5,5]Starting from any node we can visit every node in the graph in the process.
Constraints
- n == edges.length
- 2 <= n <= 10^5
- 0 <= edges[i] <= n - 1
- edges[i] != i