專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

在外賣這塊，以前本來(lái)是美團(tuán)一家獨(dú)大的，當(dāng)然還有餓了么，但餓了么體量太小，結(jié)果最近京東橫插一腳，也進(jìn)來(lái)搞外賣了，福利待遇并不輸美團(tuán)，并且還給外賣小哥上五險(xiǎn)一金，這讓不少之前跑美團(tuán)外賣的現(xiàn)在開始跑京東外賣了。

結(jié)果現(xiàn)在美團(tuán)更狠，為了應(yīng)對(duì)京東外賣的沖擊，美團(tuán)直接給商家發(fā)錢，一發(fā)就是1000億，真是夠豪橫。就在前不久，美團(tuán)外賣總經(jīng)理薛冰公開宣布，未來(lái)三年，美團(tuán)外賣將向餐飲行業(yè)整體投入1000億元，幫助餐飲伙伴健康增長(zhǎng)。這也是餐飲行業(yè)歷史上最大規(guī)模的行業(yè)扶持補(bǔ)貼計(jì)劃。

但是對(duì)于美團(tuán)這次的發(fā)錢，很多網(wǎng)友并不認(rèn)可，有網(wǎng)友說(shuō)降低傭金比什么都實(shí)惠。還有的說(shuō)是因?yàn)榫〇|外賣的布局，讓美團(tuán)有危機(jī)感了。

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

來(lái)看下今天的算法題，這題是LeetCode的第1466題：重新規(guī)劃路線，難度是中等。

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

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

今年，城市 0 將會(huì)舉辦一場(chǎng)大型比賽，很多游客都想前往城市 0 。請(qǐng)你幫助重新規(guī)劃路線方向，使每個(gè)城市都可以訪問城市 0 。返回需要變更方向的最小路線數(shù)。

題目數(shù)據(jù)保證每個(gè)城市在重新規(guī)劃路線方向后都能到達(dá)城市 0 。

示例1：

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

示例2：

輸入：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]] 輸出：2 解釋：更改以紅色顯示的路線的方向，使每個(gè)城市都可以到達(dá)城市 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]

問題分析

這題實(shí)際上說(shuō)的是給定一個(gè)有向圖，從其他所有點(diǎn)到起始點(diǎn) 0 所需要改變的路線數(shù)。

題中說(shuō)了路線網(wǎng)形成一棵樹，說(shuō)明所有點(diǎn)都是連通的并且沒有環(huán)的。我們可以從起始點(diǎn) 0 開始遍歷到其他所有點(diǎn)的路徑，因?yàn)槭菑捻旤c(diǎn) 0 開始遍歷，在路徑 中，如果是從 a 到 b 的，則路徑的改變數(shù)要加 1 ，如果是從 b 到 a 的，則路徑數(shù)不需要改變。

為什么要反著來(lái)呢？因?yàn)槲覀兪欠聪虮闅v的，題中描述的是從其他所有城市到城市 0 ，而我們計(jì)算的是從城市 0 到其他所有城市，所以要反著來(lái)算。只需要把所有頂點(diǎn)都遍歷一遍即可求出需要改變的路線數(shù)，這里我們使用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<>();     // 有向圖變成無(wú)向圖。     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 連接的節(jié)點(diǎn)。         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) ;         // 有向圖變成無(wú)向圖。         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 連接的節(jié)點(diǎn)。             if (edge.first == parent)                 continue;             ans += edge.second + dfs(edge.first, v, g);         }         return ans;     }

筆者簡(jiǎn)介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁(yè)的PDF算法文檔 。