2876. Count Visited Nodes in a Directed Graph Hard

1/**
2 * [2876] Count Visited Nodes in a Directed Graph
3 *
4 * There is a directed graph consisting of n nodes numbered from 0 to n - 1 and n directed edges.
5 * You are given a 0-indexed array edges where edges[i] indicates that there is an edge from node i to node edges[i].
6 * Consider the following process on the graph:
7 * 
8 * 	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.
9 * 
10 * 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.
11 *  
12 * <strong class="example">Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2023/08/31/graaphdrawio-1.png" />
14 * Input: edges = [1,2,0,0]
15 * Output: [3,3,3,4]
16 * Explanation: We perform the process starting from each node in the following way:
17 * - Starting from node 0, we visit the nodes 0 -> 1 -> 2 -> 0. The number of different nodes we visit is 3.
18 * - Starting from node 1, we visit the nodes 1 -> 2 -> 0 -> 1. The number of different nodes we visit is 3.
19 * - Starting from node 2, we visit the nodes 2 -> 0 -> 1 -> 2. The number of different nodes we visit is 3.
20 * - Starting from node 3, we visit the nodes 3 -> 0 -> 1 -> 2 -> 0. The number of different nodes we visit is 4.
21 * 
22 * <strong class="example">Example 2:
23 * <img alt="" src="https://assets.leetcode.com/uploads/2023/08/31/graaph2drawio.png" style="width: 191px; height: 251px;" />
24 * Input: edges = [1,2,3,4,0]
25 * Output: [5,5,5,5,5]
26 * Explanation: Starting from any node we can visit every node in the graph in the process.
27 * 
28 *  
29 * Constraints:
30 * 
31 * 	n == edges.length
32 * 	2 <= n <= 10^5
33 * 	0 <= edges[i] <= n - 1
34 * 	edges[i] != i
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/count-visited-nodes-in-a-directed-graph/
40// discuss: https://leetcode.com/problems/count-visited-nodes-in-a-directed-graph/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn count_visited_nodes(edges: Vec<i32>) -> Vec<i32> {
46        vec![]
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_2876() {
58    }
59}
60