Count Visited Nodes in a Directed Graph

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

For each node, perform DFS to find the number of unique nodes visited starting from it.
Use a state array: 0 = unvisited, 1 = visiting, 2 = visited.
If a cycle is detected, mark all nodes in the cycle and set their answer to the cycle length.
Use memoization to store the answer for each node.
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.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Cycle Detection and Memoized DFS#

Intuition#

Approach#

Code#

Complexity#