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

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

4月22日中午，有不少網友在網上發文稱京東外賣崩了，很快相關話題沖上了熱搜，如果我沒記錯的話這應該是一周之內第二次崩了，上周三的時候崩過一次，這周二的時候又崩過一次。

京東的外賣系統要的好好優化一下了，要不然三天兩頭崩，肯定不行，這樣還怎么和美團競爭。實在不行就把京東商場的程序員搞過去做，在618和雙11的時候，京東商場的下單量絕對要比京東外賣的訂單量大的多。

2023 年京東 618 累計下單金額超 4048 億元，有超 5 億用戶參與京東 618，開門紅前 10 分鐘內，京東云每秒用戶訪問峰值同比提升 129%，這么大的訂單量都沒有崩，京東外賣也完全可以讓他們去做。

劉強東為了搞外賣也是拼了，自己親自去送給外賣，還和外賣小哥一起吃飯聊天畫大餅談理想，不光是京東外賣，還和美團和餓了么的外賣小哥一起吃飯，喝酒慶祝。對于我一個消費者來說，我不希望誰干掉誰，只希望他倆都存在才是最好的。

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

來看下今天的算法題，這題是LeetCode的第1557題：可以到達所有點的最少點數目，難度是中等。

給你一個有向無環圖 ， n 個節點編號為 0 到 n-1 ，以及一個邊數組 edges ，其中 edges[i] = [fromi, toi] 表示一條從點 fromi 到點 toi 的有向邊。

找到最小的點集使得從這些點出發能到達圖中所有點。題目保證解存在且唯一。你可以以任意順序返回這些節點編號。

示例1：

輸入：n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] 輸出：[0,3] 解釋：從單個節點出發無法到達所有節點。從 0 出發我們可以到達 [0,1,2,5] 。從 3 出發我們可以到達 [3,4,2,5] 。所以我們輸出 [0,3] 。

示例2：

輸入：n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]] 輸出：[0,2,3] 解釋：注意到節點 0，3 和 2 無法從其他節點到達，所以我們必須將它們包含在結果點集中，這些點都能到達節點 1 和 4 。

• 2 <= n <= 10^5

• 1 <= edges.length <= min(10^5, n * (n - 1) / 2)

• edges[i].length == 2

• 0 <= fromi, toi < n

• 所有點對 (fromi, toi) 互不相同。

問題分析

這題說的是在一個有向無環圖中，找出最少的點集，從這些點集可以達到圖中所有的點，并且題目保證存在唯一解。

實際上這是一道和拓撲排序有關的問題，要想找出的點集最少，我們應該從入度為 0 的點開始遍歷，在圖中所有入度為 0 的點就是我們要找的點集。所以我們只需要遍歷這個有向圖，找出所有入度為 0 的頂點即可。

JAVA：

public List   findSmallestSetOfVertices(int n, List > edges)  {     int[] indegree = new int[n];// 記錄每個頂點的入度     for (List edge : edges)         indegree[edge.get(1)]++;     // 查找入度為 0 的頂點。     List ans =  new ArrayList<>();     for (int i = 0; i < n; i++)         if (indegree[i] == 0)             ans.add(i);     return ans; }

C++：

public:     vector

  findSmallestSetOfVertices(int n, vector

 > &edges) {         vector

  indegree(n, 0);// 記錄每個頂點的入度         for (const auto &edge: edges)             indegree[edge[1]]++;         // 查找入度為 0 的頂點。         vector

 ans;         for (int i = 0; i < n; i++)             if (indegree[i] == 0)                 ans.push_back(i);         return ans;     }

筆者簡介

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