讲一讲为什么要将边终点高度为第一关键字从大到小排序

题目中说：

所以我们做kruskal时应该将边终点高度为第一关键字从大到小排序

当然你可能会想：我用DFS求一遍从点1可达的边，这样子新图中不就不存在无法到达的点了吗？

但是你要知道：DFS求出的是一张有向图

而kruskal是一个针对无向图的最小生成树算法

在有向图中不合法的路径，丢到无向图中可能就合法了

所以将边终点高度为第一关键字从大到小排序，边权值为第二关键字从小到大排序是有用的

至于为什么有用嘛……我的想法是这样的（不一定对，如果有神犇明白的话可以讲讲ouo）

注：接下来提及的 “第几高” 统一指题面中每个点的 “海拔” 的值的非严格从大到小排序的顺序。以下内容可能违反“禁止在讨论区发布题解”的规定，如果违规了可以提出，我会将此帖删除

首先，如果我们用DFS/BFS求出所有的可达点，那么起点一定是最高的（如果有一条边连接着起点和比起点高的点，那么这条边在搜索中就会被 $h[u] >= h[v]$ 的限制卡住）

那么我们将边终点高度为第一关键字从大到小排序后，就会优先考虑第二高的点如何到达，接着再考虑第三高的点如何到达，以此类推……

首先考虑第二高的点如何到达，很明显，如果这种点有两个或以上，那么到达这个点的方法有两种：

第一种，从最高的点出发，这种路径毫无疑问肯定是合法的

第二种：从与他同样高的点出发，那么起点一定可以从最高的点或与他同样高的点到达（如果起点不可达，那么说明没有可以到达起点的路径，则该点在搜索时就会被排除）

如此，我们便完成了所有第二高的点的路径选择

以此类推，就可以完成所有第三高的点的路径选择，第四高的点的路径选择…直至完成所有点的路径选择（也就是完成了最小生成树）

（如果没看懂可以留言，有空可以私信ouo，有错漏之处望神犇轻喷）