2876. Count Visited Nodes in a Directed Graph
Description
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
x
and 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] 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.
Constraints:
n == edges.length
2 <= n <= 105
0 <= edges[i] <= n - 1
edges[i] != i
Solutions
Solution 1: Basic Tree + Traversal
We can use an array $ans$ to record the answer for each node, and an array $vis$ to record the visit order for each node.
For each node $i$, if it has not been visited yet, we start traversing from node $i$. There are two cases:
- If we encounter a node that has been visited before during the traversal, then we must have first entered the cycle and then walked around the cycle. For nodes outside the cycle, their answer is the length of the cycle plus the distance from the node to the cycle; for nodes inside the cycle, their answer is the length of the cycle.
- If we encounter a node that has been visited before during the traversal, then for each visited node, its answer is the distance from the current node to this node plus the answer of this node.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array edges.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
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 |
|
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 |
|
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|