Package g1401_1500.s1466_reorder_routes_to_make_all_paths_lead_to_the_city_zero

Class Solution

java.lang.Object

g1401_1500.s1466_reorder_routes_to_make_all_paths_lead_to_the_city_zero.Solution

public class Solution
extends Object

1466 - Reorder Routes to Make All Paths Lead to the City Zero.<p>Medium</p> <p>There are <code>n</code> cities numbered from <code>0</code> to <code>n - 1</code> and <code>n - 1</code> 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.</p> <p>Roads are represented by <code>connections</code> where <code>connections[i] = [a_i, b_i]</code> represents a road from city <code>a_i</code> to city <code>b_i</code>.</p> <p>This year, there will be a big event in the capital (city <code>0</code>), and many people want to travel to this city.</p> <p>Your task consists of reorienting some roads such that each city can visit the city <code>0</code>. Return the <strong>minimum</strong> number of edges changed.</p> <p>It&rsquo;s <strong>guaranteed</strong> that each city can reach city <code>0</code> after reorder.</p> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2020/05/13/sample_1_1819.png" alt="" /></p> <p><strong>Input:</strong> n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]</p> <p><strong>Output:</strong> 3</p> <p><strong>Explanation:</strong> Change the direction of edges show in red such that each node can reach the node 0 (capital).</p> <p><strong>Example 2:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2020/05/13/sample_2_1819.png" alt="" /></p> <p><strong>Input:</strong> n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]</p> <p><strong>Output:</strong> 2</p> <p><strong>Explanation:</strong> Change the direction of edges show in red such that each node can reach the node 0 (capital).</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> n = 3, connections = [[1,0],[2,0]]</p> <p><strong>Output:</strong> 0</p> <p><strong>Constraints:</strong></p> <ul> <li><code>2 <= n <= 5 * 10⁴</code></li> <li><code>connections.length == n - 1</code></li> <li><code>connections[i].length == 2</code></li> <li><code>0 <= a_i, b_i <= n - 1</code></li> <li><code>a_i != b_i</code></li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	minReorder(int n, int[][] connections)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

minReorder

public int minReorder(int n,
 int[][] connections)