无向图 union-find 最短distance ？

从面经板块抄来的。。 又没人一起讨论一下。。

https://www.1point3acres.com/bbs ... 6orderby%3Ddateline

关于图的一个题目：
给一些无向图的边（可能有环）， 问：
1）. 写一个函数，判断给的两个node是否connected
2）. 写一个函数，计算给的两个node的shortest distance （如果两个node不connected, return -1)

两个函数都会被多次掉用，要求optimize time complexity (pre-processing和真正函数的TC都要尽量小）

1）. 第一问给了个union find的solution, 表示OK
2）. Floyd–Warshall algorithm 说了，不行 ，提示说继续利用union find，没有想到什么好的方法
===
我的问题是 union-find 怎么找到俩个点的shortest distance ？？？？ 没看明白。。。 求高人指点。。。

upupupupup

感觉union find像是用在最小生成树上。但是这个貌似不是shortest distance。只能说是两个集合中最短或者是中间经过的最长路径最短。我感觉是不是想问这个。

感觉第二问其实就是dijkstra? 把tuple2<node, distance> 放进min-heap里然后用union-find来确认是否当前node已经被访问过。

每一组跑一次一次dijkstra不就行了吗