果子店面

风屏 发表于 2020-07-29 20:46:03
第二问难道不是djikstra吗

dijkstra求最短距离需要固定起点和终点，题目里需要操作很多次，每次都要花mlogn的话太慢了

idealmaster 发表于 2020-08-23 08:30:33
如果图结构是固定的话，第一问用dfs/bfs预先找出所有的连通块并标序号，之后判断两个node是不是连通看他们的连通块序号是不是相同的就行了，每次操作是真正的O(1)

第一问很容易 难的是第二问求最短距离而且要继续利用union find

游客 174.85.39.x 发表于 2020-8-23 23:35
第一问很容易 难的是第二问求最短距离而且要继续利用union find

第二问用union find找最短距离我是真想不出
我看到楼上用建树的方法也许可行，但不做path compression find的效率就无法保证