京东外卖又崩了。。。

专栏：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算法文档 。