Problem

There is a directed graph consisting of n nodes numbered from 0 to `n

  • 1andn` 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 arrayanswer whereanswer[i]_is the number ofdifferent nodes that you will visit if you perform the process starting from node _i.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

![](https://assets.leetcode.com/uploads/2023/08/31/graaphdrawio-1.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

1
2
3
4
5
6

![](https://assets.leetcode.com/uploads/2023/08/31/graaph2drawio.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 <= 10^5
  • 0 <= edges[i] <= n - 1
  • edges[i] != i

Solution

Method 1 – Cycle Detection and Memoized DFS

Intuition

Each node leads to a path that either enters a cycle or ends at a node already visited. We can use DFS with memoization to count the number of unique nodes visited from each node, marking cycles and using a visited state to avoid recomputation.

Approach

  1. For each node, perform DFS to find the number of unique nodes visited starting from it.
  2. Use a state array: 0 = unvisited, 1 = visiting, 2 = visited.
  3. If a cycle is detected, mark all nodes in the cycle and set their answer to the cycle length.
  4. Use memoization to store the answer for each node.
  5. For nodes not in a cycle, the answer is 1 + answer of the next node.

Code

 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
27
28
29
30
31
32
33
class Solution {
public:
    vector<int> countVisitedNodes(vector<int>& edges) {
        int n = edges.size();
        vector<int> ans(n, 0), state(n, 0);
        function<int(int, vector<int>&)> dfs = [&](int u, vector<int>& path) -> int {
            if (state[u] == 2) return ans[u];
            if (state[u] == 1) {
                int len = 1, v = edges[u];
                while (v != u) { len++; v = edges[v]; }
                v = u;
                do { ans[v] = len; state[v] = 2; v = edges[v]; } while (v != u);
                return len;
            }
            state[u] = 1;
            path.push_back(u);
            int res = 1 + dfs(edges[u], path);
            if (state[u] != 2) {
                ans[u] = res;
                state[u] = 2;
            }
            path.pop_back();
            return ans[u];
        };
        for (int i = 0; i < n; ++i) {
            if (state[i] == 0) {
                vector<int> path;
                dfs(i, path);
            }
        }
        return ans;
    }
};
 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
func countVisitedNodes(edges []int) []int {
    n := len(edges)
    ans := make([]int, n)
    state := make([]int, n)
    var dfs func(int, []int) int
    dfs = func(u int, path []int) int {
        if state[u] == 2 {
            return ans[u]
        }
        if state[u] == 1 {
            len := 1
            v := edges[u]
            for v != u {
                len++
                v = edges[v]
            }
            v = u
            for {
                ans[v] = len
                state[v] = 2
                v = edges[v]
                if v == u {
                    break
                }
            }
            return len
        }
        state[u] = 1
        path = append(path, u)
        res := 1 + dfs(edges[u], path)
        if state[u] != 2 {
            ans[u] = res
            state[u] = 2
        }
        return ans[u]
    }
    for i := 0; i < n; i++ {
        if state[i] == 0 {
            dfs(i, nil)
        }
    }
    return ans
}
 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
27
class Solution {
    public int[] countVisitedNodes(int[] edges) {
        int n = edges.length;
        int[] ans = new int[n], state = new int[n];
        for (int i = 0; i < n; i++) {
            if (state[i] == 0) dfs(i, edges, ans, state);
        }
        return ans;
    }
    private int dfs(int u, int[] edges, int[] ans, int[] state) {
        if (state[u] == 2) return ans[u];
        if (state[u] == 1) {
            int len = 1, v = edges[u];
            while (v != u) { len++; v = edges[v]; }
            v = u;
            do { ans[v] = len; state[v] = 2; v = edges[v]; } while (v != u);
            return len;
        }
        state[u] = 1;
        int res = 1 + dfs(edges[u], edges, ans, state);
        if (state[u] != 2) {
            ans[u] = res;
            state[u] = 2;
        }
        return ans[u];
    }
}
 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
27
28
29
30
31
32
33
class Solution {
    fun countVisitedNodes(edges: IntArray): IntArray {
        val n = edges.size
        val ans = IntArray(n)
        val state = IntArray(n)
        fun dfs(u: Int): Int {
            if (state[u] == 2) return ans[u]
            if (state[u] == 1) {
                var len = 1
                var v = edges[u]
                while (v != u) { len++; v = edges[v] }
                v = u
                do {
                    ans[v] = len
                    state[v] = 2
                    v = edges[v]
                } while (v != u)
                return len
            }
            state[u] = 1
            val res = 1 + dfs(edges[u])
            if (state[u] != 2) {
                ans[u] = res
                state[u] = 2
            }
            return ans[u]
        }
        for (i in 0 until n) {
            if (state[i] == 0) dfs(i)
        }
        return ans
    }
}
 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
27
28
29
30
31
32
class Solution:
    def countVisitedNodes(self, edges: list[int]) -> list[int]:
        n = len(edges)
        ans = [0] * n
        state = [0] * n
        def dfs(u: int) -> int:
            if state[u] == 2:
                return ans[u]
            if state[u] == 1:
                # found a cycle
                v, l = edges[u], 1
                while v != u:
                    l += 1
                    v = edges[v]
                v = u
                while True:
                    ans[v] = l
                    state[v] = 2
                    v = edges[v]
                    if v == u:
                        break
                return l
            state[u] = 1
            res = 1 + dfs(edges[u])
            if state[u] != 2:
                ans[u] = res
                state[u] = 2
            return ans[u]
        for i in range(n):
            if state[i] == 0:
                dfs(i)
        return ans
 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
27
28
29
30
31
32
33
34
35
36
37
38
39
impl Solution {
    pub fn count_visited_nodes(edges: Vec<i32>) -> Vec<i32> {
        let n = edges.len();
        let mut ans = vec![0; n];
        let mut state = vec![0; n];
        fn dfs(u: usize, edges: &Vec<i32>, ans: &mut Vec<i32>, state: &mut Vec<i32>) -> i32 {
            if state[u] == 2 { return ans[u]; }
            if state[u] == 1 {
                let mut v = edges[u] as usize;
                let mut len = 1;
                while v != u {
                    len += 1;
                    v = edges[v] as usize;
                }
                v = u;
                loop {
                    ans[v] = len;
                    state[v] = 2;
                    v = edges[v] as usize;
                    if v == u { break; }
                }
                return len;
            }
            state[u] = 1;
            let res = 1 + dfs(edges[u] as usize, edges, ans, state);
            if state[u] != 2 {
                ans[u] = res;
                state[u] = 2;
            }
            ans[u]
        }
        for i in 0..n {
            if state[i] == 0 {
                dfs(i, &edges, &mut ans, &mut state);
            }
        }
        ans
    }
}
 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
27
28
29
30
31
32
class Solution {
    countVisitedNodes(edges: number[]): number[] {
        const n = edges.length
        const ans = new Array(n).fill(0)
        const state = new Array(n).fill(0)
        function dfs(u: number): number {
            if (state[u] === 2) return ans[u]
            if (state[u] === 1) {
                let v = edges[u], len = 1
                while (v !== u) { len++; v = edges[v] }
                v = u
                do {
                    ans[v] = len
                    state[v] = 2
                    v = edges[v]
                } while (v !== u)
                return len
            }
            state[u] = 1
            const res = 1 + dfs(edges[u])
            if (state[u] !== 2) {
                ans[u] = res
                state[u] = 2
            }
            return ans[u]
        }
        for (let i = 0; i < n; ++i) {
            if (state[i] === 0) dfs(i)
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n) since each node is visited at most twice (once in DFS, once in cycle marking).
  • 🧺 Space complexity: O(n) for state and answer arrays.