题解：P12222 [蓝桥杯 2023 国 Java B] 电动车

· · 题解

思路

因为可以在城市充满电，所以答案即为无向图中最小生成树边权最大的一条边。那么用 kruskal 算法将边排序后，最后一条即第 n-1 条被加入最小生成树的边即为树中的最大边权。

如果将 m 条边遍历后被加入树中的边不为 n-1 条，那么说明图并不联通，输出 -1 即可。