2858. Minimum Edge Reversals So Every Node Is Reachable Hard

1/**
2 * [2858] Minimum Edge Reversals So Every Node Is Reachable
3 *
4 * There is a simple directed graph with n nodes labeled from 0 to n - 1. The graph would form a tree if its edges were bi-directional.
5 * You are given an integer n and a 2D integer array edges, where edges[i] = [ui, vi] represents a directed edge going from node ui to node vi.
6 * An edge reversal changes the direction of an edge, i.e., a directed edge going from node ui to node vi becomes a directed edge going from node vi to node ui.
7 * For every node i in the range [0, n - 1], your task is to independently calculate the minimum number of edge reversals required so it is possible to reach any other node starting from node i through a sequence of directed edges.
8 * Return an integer array answer, where answer[i] is the  minimum number of edge reversals required so it is possible to reach any other node starting from node i through a sequence of directed edges.
9 *  
10 * <strong class="example">Example 1:
11 * <img height="246" src="https://assets.leetcode.com/uploads/2023/08/26/image-20230826221104-3.png" width="312" />
12 * 
13 * Input: n = 4, edges = [[2,0],[2,1],[1,3]]
14 * Output: [1,1,0,2]
15 * Explanation: The image above shows the graph formed by the edges.
16 * For node 0: after reversing the edge [2,0], it is possible to reach any other node starting from node 0.
17 * So, answer[0] = 1.
18 * For node 1: after reversing the edge [2,1], it is possible to reach any other node starting from node 1.
19 * So, answer[1] = 1.
20 * For node 2: it is already possible to reach any other node starting from node 2.
21 * So, answer[2] = 0.
22 * For node 3: after reversing the edges [1,3] and [2,1], it is possible to reach any other node starting from node 3.
23 * So, answer[3] = 2.
24 * 
25 * <strong class="example">Example 2:
26 * <img height="217" src="https://assets.leetcode.com/uploads/2023/08/26/image-20230826225541-2.png" width="322" />
27 * 
28 * Input: n = 3, edges = [[1,2],[2,0]]
29 * Output: [2,0,1]
30 * Explanation: The image above shows the graph formed by the edges.
31 * For node 0: after reversing the edges [2,0] and [1,2], it is possible to reach any other node starting from node 0.
32 * So, answer[0] = 2.
33 * For node 1: it is already possible to reach any other node starting from node 1.
34 * So, answer[1] = 0.
35 * For node 2: after reversing the edge [1, 2], it is possible to reach any other node starting from node 2.
36 * So, answer[2] = 1.
37 * 
38 *  
39 * Constraints:
40 * 
41 * 	2 <= n <= 10^5
42 * 	edges.length == n - 1
43 * 	edges[i].length == 2
44 * 	0 <= ui == edges[i][0] < n
45 * 	0 <= vi == edges[i][1] < n
46 * 	ui != vi
47 * 	The input is generated such that if the edges were bi-directional, the graph would be a tree.
48 * 
49 */
50pub struct Solution {}
51
52// problem: https://leetcode.com/problems/minimum-edge-reversals-so-every-node-is-reachable/
53// discuss: https://leetcode.com/problems/minimum-edge-reversals-so-every-node-is-reachable/discuss/?currentPage=1&orderBy=most_votes&query=
54
55// submission codes start here
56
57impl Solution {
58    pub fn min_edge_reversals(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
59        vec![]
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_2858() {
71    }
72}
73