reorder-routes-to-make-all-paths-lead-to-the-city-zero

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

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.

Roads are represented by <code>connections</code> where <code>connections[i] = [ai, bi]</code> represents a road from city <code>ai</code> to city <code>bi</code>.

This year, there will be a big event in the capital (city <code>0</code>), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city <code>0</code>. Return the minimum number of edges changed.

It&#39;s guaranteed that each city can reach city <code>0</code> after reorder.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2020/05/13/sample_1_1819.png" style="width: 311px; height: 189px;" />
<pre>
Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2020/05/13/sample_2_1819.png" style="width: 509px; height: 79px;" />
<pre>
Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
Output: 2
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
</pre>

Example 3:

<pre>
Input: n = 3, connections = [[1,0],[2,0]]
Output: 0
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= n &lt;= 5 * 104</code></li>
	<li><code>connections.length == n - 1</code></li>
	<li><code>connections[i].length == 2</code></li>
	<li><code>0 &lt;= ai, bi &lt;= n - 1</code></li>
	<li><code>ai != bi</code></li>
</ul>