google ng vo 挂经

YDL-ideal

Luckyovo 发表于 2021-5-27 11:38
请问楼主知道挂在哪吗

楼主应该挂在只做了一题，后面应该还有follow up没回答

yueyingjuesha

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

yayalove

谢谢分享，楼主继续加油！谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢。

cxw111

yueyingjuesha 发表于 2021-6-7 06:10
找最小的环是如何用bfs找的，我很费解
最优的做法应该也是要O(n^3)的floyd算法

你只需要从每个节点出发，然后搜索一遍图就行了啊
https://www.geeksforgeeks.org/sh ... d-unweighted-graph/

yueyingjuesha

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

cxw111

yueyingjuesha 发表于 2021-6-16 02:03
这个算法是找无向图的最短环的，找有向图用这个算法是错的，反例就是我之前举的

hmm 没太懂你的例子，你从一个节点出发，如果是有向图，为啥会多次访问一个节点

A C
\ /
B
A->B. C->B

yueyingjuesha

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

cxw111

yueyingjuesha 发表于 2021-6-16 05:04
如果是这样的有向图：
D
/ \

ic 搜了一下，那感觉得用floy-warshall那个来算了....

Katherineaa1223

YDL-ideal 发表于 2021-6-3 09:18
利口气而伞，是不是这题

好人一生平安！

hfpt2020

我认为 rd 4需要用 floyd-warshall. Brute force can use BFS traversal starting from each node O((V+E)^2)