
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 is3.- Starting from node 1, we visit the nodes 1->2->0->1. The number of different nodes we visit is3.- Starting from node 2, we visit the nodes 2->0->1->2. The number of different nodes we visit is3.- Starting from node 3, we visit the nodes 3->0->1->2->0. The number of different nodes we visit is4.

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.
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.
classSolution {
publicint[]countVisitedNodes(int[] edges) {
int n = edges.length;
int[] ans =newint[n], state =newint[n];
for (int i = 0; i < n; i++) {
if (state[i]== 0) dfs(i, edges, ans, state);
}
return ans;
}
privateintdfs(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];
}
}
classSolution {
funcountVisitedNodes(edges: IntArray): IntArray {
val n = edges.size
val ans = IntArray(n)
val state = IntArray(n)
fundfs(u: Int): Int {
if (state[u] ==2) return ans[u]
if (state[u] ==1) {
var len = 1var 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] = 1val res = 1 + dfs(edges[u])
if (state[u] !=2) {
ans[u] = res
state[u] = 2 }
return ans[u]
}
for (i in0 until n) {
if (state[i] ==0) dfs(i)
}
return ans
}
}
classSolution:
defcountVisitedNodes(self, edges: list[int]) -> list[int]:
n = len(edges)
ans = [0] * n
state = [0] * n
defdfs(u: int) -> int:
if state[u] ==2:
return ans[u]
if state[u] ==1:
# found a cycle v, l = edges[u], 1while v != u:
l +=1 v = edges[v]
v = u
whileTrue:
ans[v] = l
state[v] =2 v = edges[v]
if v == u:
breakreturn l
state[u] =1 res =1+ dfs(edges[u])
if state[u] !=2:
ans[u] = res
state[u] =2return ans[u]
for i in range(n):
if state[i] ==0:
dfs(i)
return ans
impl Solution {
pubfncount_visited_nodes(edges: Vec<i32>) -> Vec<i32> {
let n = edges.len();
letmut ans =vec![0; n];
letmut state =vec![0; n];
fndfs(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 {
letmut v = edges[u] asusize;
letmut len =1;
while v != u {
len +=1;
v = edges[v] asusize;
}
v = u;
loop {
ans[v] = len;
state[v] =2;
v = edges[v] asusize;
if v == u { break; }
}
return len;
}
state[u] =1;
let res =1+ dfs(edges[u] asusize, edges, ans, state);
if state[u] !=2 {
ans[u] = res;
state[u] =2;
}
ans[u]
}
for i in0..n {
if state[i] ==0 {
dfs(i, &edges, &mut ans, &mut state);
}
}
ans
}
}