Watch 7 video solutions for Count Visited Nodes in a Directed Graph, a hard level problem involving Dynamic Programming, Graph, Memoization. This walkthrough by codingMohan has 3,043 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |