專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

在外賣這塊，以前本來是美團一家獨大的，當然還有餓了么，但餓了么體量太小，結果最近京東橫插一腳，也進來搞外賣了，福利待遇并不輸美團，并且還給外賣小哥上五險一金，這讓不少之前跑美團外賣的現在開始跑京東外賣了。

結果現在美團更狠，為了應對京東外賣的沖擊，美團直接給商家發錢，一發就是1000億，真是夠豪橫。就在前不久，美團外賣總經理薛冰公開宣布，未來三年，美團外賣將向餐飲行業整體投入1000億元，幫助餐飲伙伴健康增長。這也是餐飲行業歷史上最大規模的行業扶持補貼計劃。

但是對于美團這次的發錢，很多網友并不認可，有網友說降低傭金比什么都實惠。還有的說是因為京東外賣的布局，讓美團有危機感了。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第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 。

• 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]

問題分析

這題實際上說的是給定一個有向圖，從其他所有點到起始點 0 所需要改變的路線數。

題中說了路線網形成一棵樹，說明所有點都是連通的并且沒有環的。我們可以從起始點 0 開始遍歷到其他所有點的路徑，因為是從頂點 0 開始遍歷，在路徑 中，如果是從 a 到 b 的，則路徑的改變數要加 1 ，如果是從 b 到 a 的，則路徑數不需要改變。

為什么要反著來呢？因為我們是反向遍歷的，題中描述的是從其他所有城市到城市 0 ，而我們計算的是從城市 0 到其他所有城市，所以要反著來算。只需要把所有頂點都遍歷一遍即可求出需要改變的路線數，這里我們使用DFS遍歷。

JAVA：

public int minReorder(int n, int[][] connections) {     List

 [] g = new List[n];     for (int i = 0; i < n; i++)         g[i] = new ArrayList<>();     // 有向圖變成無向圖。     for (int[] edge : connections) {         // 指向別人的需要反向，讓別人指向自己，所以加1.         g[edge[0]].add(newint[]{edge[1], 1});         // 指向自己的不需要反向。         g[edge[1]].add(newint[]{edge[0], 0});     }     return dfs(0, -1, g); } private int dfs(int v, int parent, List

 [] g) {     int ans = 0;     for (int[] edge : g[v]) {// 遍歷 v 連接的節點。         if (edge[0] == parent)             continue;         ans += edge[1] + dfs(edge[0], v, g);     }     return ans; }

C++：

public:     int minReorder(int n, vector

 > &connections) {         vector

 >>  g (n) ;         // 有向圖變成無向圖。         for (constauto &edge: connections) {             // 指向別人的需要反向，讓別人指向自己，所以加1.             g[edge[0]].emplace_back(edge[1], 1);             // 指向自己的不需要反向。             g[edge[1]].emplace_back(edge[0], 0);         }         return dfs(0, -1, g);     }     int dfs(int v, int parent, const vector

 >> &g)  {         int ans = 0;         for (constauto &edge: g[v]) {// 遍歷 v 連接的節點。             if (edge.first == parent)                 continue;             ans += edge.second + dfs(edge.first, v, g);         }         return ans;     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。