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:
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.length2 <= n <= 1050 <= edges[i] <= n - 1edges[i] != iProblem Overview: You are given a directed graph where each node has exactly one outgoing edge. Starting from every node, you keep following edges until a node repeats. The task is to compute how many unique nodes are visited for each starting node.
This structure forms a collection of chains that eventually enter cycles. The key challenge is handling cycles correctly while reusing previously computed results for nodes that lead into those cycles.
Approach 1: DFS with Cycle Detection and Memoization (O(n) time, O(n) space)
Treat the graph as a functional graph (each node has one outgoing edge) and run DFS from each node. Maintain three states for nodes: unvisited, visiting, and processed. When DFS encounters a node already marked as visiting, a cycle is detected. Compute the cycle length and assign that value to all nodes in the cycle. For nodes outside the cycle, propagate results using dp[node] = 1 + dp[next]. Memoization ensures each node is processed once, giving overall O(n) time and O(n) space.
This approach combines graph traversal with dynamic programming. Once a node's result is computed, future DFS calls reuse it instantly. Cycle detection is the critical insight because nodes inside a cycle share the same reachable count.
Approach 2: Iterative Cycle Detection with Path Compression (O(n) time, O(n) space)
An iterative strategy avoids recursion by walking the path from each unprocessed node while storing the traversal order in a stack or list. When the walk reaches a previously visited node, two cases appear: either a cycle is found in the current path or the path merges into a node whose answer is already known.
If a cycle appears, determine its length and assign that value to all nodes inside the cycle. For nodes before the cycle, process the path in reverse order and compute dp[node] = dp[next] + 1. This acts like path compression where each node’s result is finalized exactly once.
The iterative approach is often preferred in languages with recursion limits. It still achieves O(n) time because each node is pushed and processed a constant number of times. The algorithm relies heavily on memoization and careful bookkeeping of node states.
Recommended for interviews: The DFS with cycle detection and memoization approach is usually the most intuitive explanation during interviews. It clearly shows understanding of functional graphs, cycle handling, and dynamic programming reuse. The iterative path-compression variant demonstrates deeper optimization and control over recursion, but both achieve the optimal O(n) complexity expected for this problem.
This approach uses Depth First Search (DFS) to explore each node and detect cycles. Each node keeps track of the nodes visited to count distinct visits. The detection of cycles ensures efficient avoidance of repeated loops.
We track visited nodes using a list where the index represents each node and its value represents whether the node was visited during this process. The method leverages a DFS pattern where each node's path is traversed, recording the path in a stack and leveraging a set for cycle detection.
Time complexity: O(n) where n is the number of nodes as each node is visited at most once.
Space complexity: O(n) for auxiliary data structures.
This approach implements an iterative approach to detect cycles and uses path compression techniques to consolidate previous results for repeated nodes. It arrays thorough edge exploration, directly adjusting visited node counts efficiently.
This Python code iteratively traverses through each node, marking nodes along the path as visited. If a node previously visits within the same path, counting signals a cycle start. Else collected path-length is assigned to non-repeating nodes.
Time complexity: O(n).
Space complexity: O(n).
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:
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array edges.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| DFS Approach with Cycle Detection | Time complexity: O(n) where n is the number of nodes as each node is visited at most once. |
| Iterative Cycle Detection and Path Compression | Time complexity: O(n). |
| Basic Tree + Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Cycle Detection and Memoization | O(n) | O(n) | Most common interview approach; clear recursion and DP reuse |
| Iterative Cycle Detection with Path Compression | O(n) | O(n) | Avoid recursion limits and process paths iteratively |
2876. Count Visited Nodes in a Directed Graph | Weekly Leetcode 365 • codingMohan • 3,043 views views
Watch 6 more video solutions →Practice Count Visited Nodes in a Directed Graph with our built-in code editor and test cases.
Practice on FleetCode