Count Visited Nodes in a Directed Graph - Solution & Explanation
Problem Statement
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] 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] != i
Approach Overview
Problem 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.
Approach 1: DFS Approach with Cycle Detection
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.
Complexity
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.
Approach 2: Iterative Cycle Detection and Path Compression
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.
Complexity
Time complexity: O(n).
Space complexity: O(n).
Approach 3: 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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
2876. Count Visited Nodes in a Directed Graph | Weekly Leetcode 365 • codingMohan • 3,131 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Count Visited Nodes in a Directed Graph easy or hard?
How to solve Count Visited Nodes in a Directed Graph in O(n)?
Count Visited Nodes in a Directed Graph Python or Java solution?
What is the best approach for Count Visited Nodes in a Directed Graph?
What data structure is used in Count Visited Nodes in a Directed Graph?
What is the time complexity of Count Visited Nodes in a Directed Graph?
Is Count Visited Nodes in a Directed Graph asked at Google or other top companies?
Ready to solve this problem?
Practice Count Visited Nodes in a Directed Graph with our built-in code editor and test cases.
Practice on FleetCode