Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間1年前 (2023/03/24 18:02)推噓2(2推 0噓 1→)

留言3則, 3人參與討論串271/719 (看更多)

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