付費限定

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

更新於 發佈於 閱讀時間約 8 分鐘

題目敘述

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

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

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

註:

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


題目的原文敘述


測試範例

Example 1:

raw-image
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:

raw-image
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

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

  • ai != bi
以行動支持創作者!付費即可解鎖
本篇內容共 3482 字、4 則留言,僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容,可能因為尚未登入,或沒有該房間的查看權限。
avatar-img
92會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目敘述 題目會給我們一串相鄰矩陣isConnected,相鄰矩陣的元素值isConnected[i][j] 代表第i座城市和第j座城市是否有連通。 如果彼此有連通,則isConnected[i][j]=1。 如果彼此沒有連通,則isConnected[i][j]=0。 彼此互相有路徑可以
題目敘述 題目會給我們一棵BST二元搜索樹的根結點root,還有一個指定的目標值key。 要求我們在樹中刪除帶有這個key值的節點,並且返回更新過後二元搜索樹的樹根root。 題目的原文敘述 測試範例 Example 1: Input: root = [5,3,6,2,4,null,
題目敘述 題目會給我們一棵二元搜索樹的根結點root,還有一個指定的目標值val。 要求我們找出在樹中對應到目標值val的節點,假如找不到,請回傳null( null在Python就是None)。 題目的原文敘述 測試範例 Example 1: Input: root = [4,2,
題目敘述 題目會給我們一棵二元樹的根結點,要求我們找出哪一層擁有最大的水平元素和(Level-sum)? 題目的原文敘述 測試範例 Example 1: Input: root = [1,7,0,7,-8,null,null] Output: 2 Explanation: Level
題目敘述 題目會給定一顆二元樹的根結點Root node,和這棵樹中的任意兩個節點p, q。 請找出p, q 在這棵二元數裡面的最接近公共祖先節點是誰? 最接近的公共節點: 就是p, q兩個節點從下往上走,第一個交會的節點。 題目的原文敘述 測試範例 Example 1: Inpu
題目敘述 題目會給我們一顆二元樹的根節點。請問在這棵樹中,之字型走法的路徑長度最大值是多少? 如果無解,請返回 零。 註: 之字型走法就是有一段路徑,都是由連續的 左右左右...,或者 右左右左...所構成的路徑。(看下方的測試範例會更清楚題目的定義) 題目的原文敘述 測試範例 E
題目敘述 題目會給我們一串相鄰矩陣isConnected,相鄰矩陣的元素值isConnected[i][j] 代表第i座城市和第j座城市是否有連通。 如果彼此有連通,則isConnected[i][j]=1。 如果彼此沒有連通,則isConnected[i][j]=0。 彼此互相有路徑可以
題目敘述 題目會給我們一棵BST二元搜索樹的根結點root,還有一個指定的目標值key。 要求我們在樹中刪除帶有這個key值的節點,並且返回更新過後二元搜索樹的樹根root。 題目的原文敘述 測試範例 Example 1: Input: root = [5,3,6,2,4,null,
題目敘述 題目會給我們一棵二元搜索樹的根結點root,還有一個指定的目標值val。 要求我們找出在樹中對應到目標值val的節點,假如找不到,請回傳null( null在Python就是None)。 題目的原文敘述 測試範例 Example 1: Input: root = [4,2,
題目敘述 題目會給我們一棵二元樹的根結點,要求我們找出哪一層擁有最大的水平元素和(Level-sum)? 題目的原文敘述 測試範例 Example 1: Input: root = [1,7,0,7,-8,null,null] Output: 2 Explanation: Level
題目敘述 題目會給定一顆二元樹的根結點Root node,和這棵樹中的任意兩個節點p, q。 請找出p, q 在這棵二元數裡面的最接近公共祖先節點是誰? 最接近的公共節點: 就是p, q兩個節點從下往上走,第一個交會的節點。 題目的原文敘述 測試範例 Example 1: Inpu
題目敘述 題目會給我們一顆二元樹的根節點。請問在這棵樹中,之字型走法的路徑長度最大值是多少? 如果無解,請返回 零。 註: 之字型走法就是有一段路徑,都是由連續的 左右左右...,或者 右左右左...所構成的路徑。(看下方的測試範例會更清楚題目的定義) 題目的原文敘述 測試範例 E
你可能也想看
Google News 追蹤
Thumbnail
在創作的路上真的很多人問我說 到底要怎麼做出符合自己期待 但又可以表現得很有美感的作品?🥹 這個問題真的應該是每個創作者都一直在學習的課題吧!
提問的內容越是清晰,強者、聰明人越能在短時間內做判斷、給出精準的建議,他們會對你產生「好印象」,認定你是「積極」的人,有機會、好人脈會不自覺地想引薦給你
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點, 要求我們計算滿足局部路徑節點和=targetSum的數目有多少? 註: 局部路徑節點和 =由節點a往下走到某個節點b,這個區間內的節點值總和 題目的原文敘述 測試範例 Example 1: Input: root = [10,5,-3,3
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點,要求我們判定這是否為一顆合法的奇偶二元樹? 奇偶二元樹的定義: 從上到下依序是第0層、第一層、...、第n層 偶數層裡面的節點值都必須是奇數,而且由左到右嚴格遞增。 奇數層裡面的節點值都必須是偶數,而且由左到右嚴格遞減。 題目的原文敘述 測試
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點,要求我們找出這棵二元樹最後一層最左邊的值。 題目的原文敘述 測試範例 Example 1: Input: root = [2,1,3] Output: 1 Example 2: Input: root = [1,2,3,4,null,5,6
Thumbnail
題目敘述 題目會給定一個二維陣列grid,代表每顆橘子分布的位置和初始狀態。 0: 這個格子點沒有東西。 1: 這個格子點有一顆新鮮的橘子。 2: 這個格子點有一顆壞掉的橘子。 壞掉的橘子上面的黴菌, 每隔一個週期,可以向上、下、左、右 N4四連通的格子點感染一次。 請問,最少需要多
Thumbnail
在創作的路上真的很多人問我說 到底要怎麼做出符合自己期待 但又可以表現得很有美感的作品?🥹 這個問題真的應該是每個創作者都一直在學習的課題吧!
提問的內容越是清晰,強者、聰明人越能在短時間內做判斷、給出精準的建議,他們會對你產生「好印象」,認定你是「積極」的人,有機會、好人脈會不自覺地想引薦給你
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點, 要求我們計算滿足局部路徑節點和=targetSum的數目有多少? 註: 局部路徑節點和 =由節點a往下走到某個節點b,這個區間內的節點值總和 題目的原文敘述 測試範例 Example 1: Input: root = [10,5,-3,3
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點,要求我們判定這是否為一顆合法的奇偶二元樹? 奇偶二元樹的定義: 從上到下依序是第0層、第一層、...、第n層 偶數層裡面的節點值都必須是奇數,而且由左到右嚴格遞增。 奇數層裡面的節點值都必須是偶數,而且由左到右嚴格遞減。 題目的原文敘述 測試
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點,要求我們找出這棵二元樹最後一層最左邊的值。 題目的原文敘述 測試範例 Example 1: Input: root = [2,1,3] Output: 1 Example 2: Input: root = [1,2,3,4,null,5,6
Thumbnail
題目敘述 題目會給定一個二維陣列grid,代表每顆橘子分布的位置和初始狀態。 0: 這個格子點沒有東西。 1: 這個格子點有一顆新鮮的橘子。 2: 這個格子點有一顆壞掉的橘子。 壞掉的橘子上面的黴菌, 每隔一個週期,可以向上、下、左、右 N4四連通的格子點感染一次。 請問,最少需要多