Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2023-03-24 18:02:08
1466. Reorder Routes to Make All Paths Lead to the City Zero
有n個城市,編號從0到n-1,有n-1條道路,道路由connections表示,其中
connections[i] = [ai, bi]表示從城市ai到城市bi的道路,每個城市
間只會有一條路可以走且是單行道。
城市0將舉辦一個活動,我們的任務是重新定向一些單行道,以便每個城市都能
夠到達城市0。返回更改的最小邊數,可以確保每個城市的道路改向後都能到達城市0。
Example :
https://assets.leetcode.com/uploads/2020/05/13/sample_1_1819.png
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).
思路:
1.道路都是單行道不過我們可以先把整個圖當作是一個無向圖,從0開始出發做DFS,
檢查下個目的地是否存在"往起點方向"的路徑。
2.我們用負的值來表示反方向的目的地,如果下個目的地無法回到起點就讓ans遞增。
3.因為是無向圖所以要記錄上個點避免進入迴圈。
Java Code:
作者: a1234555 (肉寶寶)   2022-03-24 18:02:00
大師
作者: MurasakiSion (紫咲シオン)   2023-03-24 18:04:00
大師
作者: Che31128 (justjoke)   2023-03-24 18:10:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com