→ a1234555: 大師 03/24 18:02
推 MurasakiSion: 大師 03/24 18:04
推 Che31128: 大師 03/24 18:10
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：
------------------------------------
class Solution {
private int ans;
public int minReorder(int n, int[][] connections) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] connection : connections) {
graph.get(connection[0]).add(connection[1]);
graph.get(connection[1]).add(-connection[0]);
}
ans = 0;
dfs(graph,-1, 0);
return ans;
}
private void dfs(List<List<Integer>> graph, int prev, int i) {
for (int next : graph.get(i)) {
if (Math.abs(next) == prev) continue;
ans += next < 0 ? 0 : 1;
dfs(graph, i, Math.abs(next));
}
}
}
------------------------------------
--
https://i.imgur.com/bFRiqA3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1679652131.A.A52.html