付費限定文章

圖論應用: 改變邊的方向，讓所有路徑都指向同一個城市_Leetcode #1466_Leetcode 75精選

愚木混株 cdd20 on Unsplash

題目敘述

題目會給定我們一個輸入陣列connections，和城市的總數目n。

輸入陣列裡面是以pair的方式儲存，(a, b) 分邊代表這條邊的起點和終點。

請問，我們需要改變多少條邊的方向，才能讓每條路徑都指向編號零號的城市( City #0)？

註:

題目還保證，在改變方向之後，一定可以讓每座城市都有路徑可以抵達編號零號的城市( City #0)，也就是說，不會有孤立的城市。

題目的原文敘述

測試範例

Example 1:

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).
我們需要反轉三條邊的方向，才能讓所有路徑都指向第零座城市。
分別是​[0, 1], [1, 3], [4, 5]

Example 2:

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).
我們需要反轉2條邊的方向，才能讓所有路徑都指向第零座城市。
分別是​[1, 2], [3, 4]

Example 3:

Input: n = 3, connections = [[1,0],[2,0]]
Output: 0
不需要反轉，就已經是每條路徑​都指向第零座城市。

約束條件

Constraints:

• 2 <= n <= 5 * 10^4

城市的數目介於 2 ~ 五萬之間。

• connections.length == n - 1

輸入陣列長度 = 城市的總數目 - 1

• connections[i].length == 2

輸入陣列內每個元素都是一組pair，分別代表起點、終點。

• 0 <= ai, bi <= n - 1

所有起點和終點編號都是合法的值。