这道题建的新图应该是搜索时搜到的边组成的,而非一开始满足 h[u] >= h[v] 或者 h[v] >= h[u] 的。原因可以考虑当一个景点不可达仍然会把它和比它低的连边,然而 kruskal 记录时没有方向,也就是说它可能被选进生成树里面,但这个显然不对。即,注意边的有向性。
h[u] >= h[v]
h[v] >= h[u]