果子店面

关于图的一个题目：
给一些无向图的边（可能有环）， 问：
1

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

all algorithm 说了，不行 ，提示说继续利用union find，没有想到什么好的方法

第二问难道不是djikstra吗

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

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

第一个题用topology sort？ 第二题感觉就是用BFS就可以了吧？

關注一下 坐等大神解答

马克一下，等解答

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

马克一下，等解答

非要接着union find做能不能建union find的时候不update parent，这样就变成了一个tree，然后可以找到共同的common node，再计算两点到common node的距离和？复杂度树的depth

感觉遇到了非常相似的面试官。。lz是哪个组？

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