🚀 算法題 🚀

🌲 算法刷題專欄 | 面試必備算法 | 面試高頻算法 🍀
🌲 越難的東西,越要努力堅持，因為它具有很高的價值，算法就是這樣?
🌲 作者簡介：碩風和煒，CSDN-Java領域新星創作者🏆，保研|國家獎學金|高中學習JAVA|大學完善JAVA開發技術棧|面試刷題|面經八股文|經驗分享|好用的網站工具分享💎💎💎
🌲 恭喜你發現一枚寶藏博主,趕快收入囊中吧🌻
🌲 人生如棋，我愿為卒，行動雖慢，可誰曾見我后退一步？🎯🎯

🚀 算法題 🚀

🚩 題目鏈接

• 1466. 重新規劃路線

? 題目描述

n 座城市，從 0 到 n-1 編號，其間共有 n-1 條路線。因此，要想在兩座不同城市之間旅行只有唯一一條路線可供選擇（路線網形成一顆樹）。去年，交通運輸部決定重新規劃路線，以改變交通擁堵的狀況。

路線用 connections 表示，其中 connections[i] = [a, b] 表示從城市 a 到 b 的一條有向路線。

今年，城市 0 將會舉辦一場大型比賽，很多游客都想前往城市 0 。

請你幫助重新規劃路線方向，使每個城市都可以訪問城市 0 。返回需要變更方向的最小路線數。

題目數據 保證 每個城市在重新規劃路線方向后都能到達城市 0 。

示例 1：

輸入：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
輸出：3
解釋：更改以紅色顯示的路線的方向，使每個城市都可以到達城市 0 。
示例 2：

輸入：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
輸出：2
解釋：更改以紅色顯示的路線的方向，使每個城市都可以到達城市 0 。
示例 3：

輸入：n = 3, connections = [[1,0],[2,0]]
輸出：0

提示：

2 <= n <= 5 * 10^4
connections.length == n-1
connections[i].length == 2
0 <= connections[i][0], connections[i][1] <= n-1
connections[i][0] != connections[i][1]

🌟 求解思路&實現代碼&運行結果

---

? DFS + 圖 + 樹

🥦 求解思路

1. 給定的n個點，n?1條邊構成的有向圖，題目的要求是，重新規劃路線，更改不能到達0的方向路線，最后求所有點到0點最小改變次數。
2. 可以忽略邊的方向，有向圖直接變成了一棵樹。需要改變某些邊的方向使得每個點都可以訪問到 0點，那么我們從0節點開始，通過dfs(son,father)來求解整個過程。
3. 同時，在進行dfs之前，我們需要標記代價，connections原始方向使用1標記原方向的邊，使用0標記反向邊。
4. 實現代碼如下所示：

🥦 實現代碼

class Solution {private ArrayList<int[]>[] list;public int minReorder(int n, int[][] connections) {this.list=new ArrayList[n];Arrays.setAll(list,e->new ArrayList<>());for(int[] conn:connections){list[conn[0]].add(new int[]{conn[1],1});list[conn[1]].add(new int[]{conn[0],0});}return dfs(0,-1);}public int dfs(int x,int father){int ans=0;for(int[] next:list[x]){if(father!=next[0]){ans+=next[1]+dfs(next[0],x);}}return ans;}}

🥦 運行結果

---

💬 共勉

最后，我想和大家分享一句一直激勵我的座右銘，希望可以與大家共勉！