1466. Reorder Routes to Make All Paths Lead to the City Zero Medium

1/**
2 * [1466] Reorder Routes to Make All Paths Lead to the City Zero
3 *
4 * There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.
5 * Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi.
6 * This year, there will be a big event in the capital (city 0), and many people want to travel to this city.
7 * Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.
8 * It's guaranteed that each city can reach city 0 after reorder.
9 *  
10 * Example 1:
11 * <img alt="" src="https://assets.leetcode.com/uploads/2020/05/13/sample_1_1819.png" style="width: 311px; height: 189px;" />
12 * Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
13 * Output: 3
14 * Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
15 * 
16 * Example 2:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2020/05/13/sample_2_1819.png" style="width: 509px; height: 79px;" />
18 * Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
19 * Output: 2
20 * Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
21 * 
22 * Example 3:
23 * 
24 * Input: n = 3, connections = [[1,0],[2,0]]
25 * Output: 0
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	2 <= n <= 5 * 10^4
31 * 	connections.length == n - 1
32 * 	connections[i].length == 2
33 * 	0 <= ai, bi <= n - 1
34 * 	ai != bi
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/
40// discuss: https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn min_reorder(n: i32, connections: Vec<Vec<i32>>) -> i32 {
46        0
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_1466() {
58    }
59}
60