# Count Visited Nodes in a Directed Graph
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-visited-nodes-in-a-directed-graph)
Canonical: https://scaleengineer.com/dsa/problems/count-visited-nodes-in-a-directed-graph
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Data structures:** Graph
**Companies:** [BNY Mellon](https://scaleengineer.com/companies/bny-mellon)
---
## Problem
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:**

![](https://assets.glich.co/dsa/count-visited-nodes-in-a-directed-graph/image0.png) 

**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:**

![](https://assets.glich.co/dsa/count-visited-nodes-in-a-directed-graph/image1.png) 

**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`

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem for each starting node. For every node from `0` to `n-1`, we traverse the graph, keeping track of the nodes visited in the current path using a HashSet. The traversal stops when we encounter a node that has already been seen in this specific traversal. The number of nodes collected in the HashSet gives us the answer for the starting node.
**Time:** O(n^2) - For each of the `n` starting nodes, the traversal can take up to O(n) steps in the worst case (a single long path). This results in a quadratic time complexity. · **Space:** O(n) - In each simulation, the `HashSet` can store up to `n` nodes in the worst-case scenario where the path traverses all nodes before repeating.
**Pros:** Simple to understand and implement.; Directly follows the logic described in the problem statement.
**Cons:** Highly inefficient due to redundant computations. The traversal from one node might largely overlap with the traversal from another, but this work is repeated.; The time complexity is too high for the given constraints, which will likely result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
We initialize an `answer` array of size `n`. We then iterate through each node `i` from `0` to `n-1` to calculate `answer[i]`. For each `i`, we begin a simulation. A `HashSet` called `visited_in_path` is used to store nodes visited in the current traversal, which starts from node `i`. We also use a counter, `count`, initialized to 0. We start with `currentNode = i`. In a loop, as long as `currentNode` is not in `visited_in_path`, we add it to the set, increment our count, and move to the next node by setting `currentNode = edges[currentNode]`. When the loop terminates, it means we've encountered a node that was already in `visited_in_path`. The final value of `count` (or the size of the set) is the number of different nodes visited, which we store in `answer[i]`. After iterating through all possible starting nodes, the `answer` array is complete and returned.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] countVisitedNodes(int[] edges) {
        int n = edges.length;
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            Set<Integer> visitedInPath = new HashSet<>();
            int currentNode = i;
            while (visitedInPath.add(currentNode)) {
                currentNode = edges[currentNode];
            }
            answer[i] = visitedInPath.size();
        }

        return answer;
    }
}
```
### Algorithm
- Create an integer array `answer` of size `n`.
- For each node `i` from `0` to `n-1`:
    - Create a `HashSet<Integer>` `pathVisited` to keep track of nodes visited in the current traversal.
    - Initialize `currentNode = i`.
    - In a loop, continue as long as `currentNode` can be added to `pathVisited` (meaning it's a new node for this path).
        - In each iteration, update `currentNode` to `edges[currentNode]`.
    - The size of `pathVisited` is the number of unique nodes visited. Store this in `answer[i]`.
- Return the `answer` array.

## DFS with Memoization
This approach improves upon the brute force method by using memoization to avoid re-computation. We use an `answer` array to store the results. When we traverse from a node, if we encounter another node whose result is already known, we can use that result to quickly calculate the answers for all nodes in the current path. This ensures that each node's answer is computed exactly once, leading to a linear time complexity.
**Time:** O(n) - Each node is visited a constant number of times across all traversals. Once a node's answer is computed, it's never part of a traversal path again, effectively making the total work proportional to the number of nodes. · **Space:** O(n) - We need O(n) for the `answer` array. The `path` map used during a traversal can also grow up to O(n) in the worst case of a single component containing all nodes.
**Pros:** Highly efficient with linear time complexity, making it suitable for large inputs.; Avoids redundant computations by storing and reusing results (memoization).
**Cons:** More complex to implement compared to the brute force approach.; Requires careful handling of the two termination cases: finding a cycle versus hitting a pre-computed path.
### Explanation
The key insight is that the path from any node `i` will eventually enter a cycle or merge with a path whose properties are already known. We can exploit this structure.

We use an `answer` array of size `n`, initialized to zeros. A non-zero value `answer[i]` means the result for node `i` is known.

We iterate from `i = 0` to `n-1`. If `answer[i]` is zero, we initiate a traversal. During this traversal, we use a `HashMap` to keep track of the nodes in the current path and their respective distances from the starting node `i`. The traversal `curr = edges[curr]` continues until we hit a node `curr` that either has a non-zero `answer` or is already in our path map.

If `answer[curr]` is non-zero, we've reached a segment of the graph for which we have answers. We can then backtrack along the path we just traversed, calculating the answer for each node based on `answer[curr]` and its distance to `curr`.

If `curr` is already in our path map, we've detected a cycle. We can calculate the cycle's length and the length of the path leading to it. All nodes within the cycle will have the cycle length as their answer. Nodes on the path leading to the cycle will have an answer equal to the cycle length plus their distance to the cycle's entry point.

By storing results, we ensure every node is fully processed only once.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] countVisitedNodes(int[] edges) {
        int n = edges.length;
        int[] answer = new int[n]; // 0 indicates not calculated yet

        for (int i = 0; i < n; i++) {
            if (answer[i] == 0) {
                // Start traversal from node i
                int dist = 0;
                int curr = i;
                Map<Integer, Integer> path = new HashMap<>();

                // Traverse until we find a cycle or a node with a known answer
                while (answer[curr] == 0 && !path.containsKey(curr)) {
                    path.put(curr, dist);
                    dist++;
                    curr = edges[curr];
                }

                if (path.containsKey(curr)) { // Cycle detected in the current traversal
                    int cycleStartDist = path.get(curr);
                    int cycleLen = dist - cycleStartDist;
                    
                    for (Map.Entry<Integer, Integer> entry : path.entrySet()) {
                        if (entry.getValue() >= cycleStartDist) {
                            // Node is in the cycle
                            answer[entry.getKey()] = cycleLen;
                        } else {
                            // Node is on the path leading to the cycle
                            answer[entry.getKey()] = cycleLen + (cycleStartDist - entry.getValue());
                        }
                    }
                } else { // Hit a node with a pre-computed answer
                    int knownLen = answer[curr];
                    for (Map.Entry<Integer, Integer> entry : path.entrySet()) {
                        answer[entry.getKey()] = knownLen + (dist - entry.getValue());
                    }
                }
            }
        }
        return answer;
    }
}
```
### Algorithm
- Initialize an `answer` array of size `n` with all zeros. A zero indicates the answer for that node has not been computed.
- Iterate through each node `i` from `0` to `n-1`.
- If `answer[i]` is 0, start a traversal from `i`:
    - Use a `Map<Integer, Integer>` called `path` to store each node in the current traversal path and its distance from the starting node.
    - Traverse from `curr = i`, incrementing distance, until `curr` is a node that is already in `path` (a cycle is found) or `answer[curr]` is non-zero (a previously computed path is reached).
    - **Case 1: Cycle found.** The node `curr` is already in `path`. Calculate the cycle length. For all nodes in the cycle, the answer is the cycle length. For all nodes on the path leading to the cycle, the answer is `(distance to cycle) + (cycle length)`.
    - **Case 2: Known path reached.** `answer[curr]` is non-zero. The answer for any node `u` in the current `path` is `answer[curr] + (distance from u to curr)`.
- Update the `answer` array for all nodes visited in the current traversal.
- Return `answer`.

# Solutions
### Java

```java
class Solution { public int [] countVisitedNodes ( List < Integer > edges ) { int n = edges . size (); int [] ans = new int [ n ]; int [] vis = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { if ( ans [ i ] == 0 ) { int cnt = 0 , j = i ; while ( vis [ j ] == 0 ) { vis [ j ] = ++ cnt ; j = edges . get ( j ); } int cycle = 0 , total = cnt + ans [ j ]; if ( ans [ j ] == 0 ) { cycle = cnt - vis [ j ] + 1 ; } j = i ; while ( ans [ j ] == 0 ) { ans [ j ] = Math . max ( total --, cycle ); j = edges . get ( j ); } } } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  vector<int> countVisitedNodes(vector<int> &edges) {
    int n = edges.size();
    vector<int> ans(n), vis(n);
    for (int i = 0; i < n; ++i) {
      if (!ans[i]) {
        int cnt = 0, j = i;
        while (vis[j] == 0) {
          vis[j] = ++cnt;
          j = edges[j];
        }
        int cycle = 0, total = cnt + ans[j];
        if (ans[j] == 0) {
          cycle = cnt - vis[j] + 1;
        }
        j = i;
        while (ans[j] == 0) {
          ans[j] = max(total--, cycle);
          j = edges[j];
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countVisitedNodes(self, edges: List[int]) -> List[int]: n = len(edges) ans = [0] * n vis = [0] * n for i in range(n): if not ans[i]: cnt, j = 0, i while not vis[j]: cnt += 1 vis[j] = cnt j = edges[j] cycle, total = 0, cnt + ans[j] if not ans[j]: cycle = cnt - vis[j] + 1 total = cnt j = i while not ans[j]: ans[j] = max(total, cycle) total -= 1 j = edges[j] return ans

```