咕狗实习挂经+详细Timeline

mysteryjoe 发表于 2019-1-31 08:16
所以保证能去success node是说从某点出发走任意路径都会到success node吗

差不多，也就是从出发的node开始不管怎么走都能到success node

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

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

pandami 发表于 2019-1-31 09:15
加面可以考虑一下topological sort
改一改应该可以

topological sort能检测loop嘛？我没怎么真正用过topological sort。这题主要就是loop不好处理

shawnchan2014 发表于 2019/01/31 09:46:50


topological sort能检测loop嘛？我没怎么真正用过topological sort。这题主要就是loop不好处理

topo sort最后queue里剩下的都是loop

shawnchan2014 发表于 2019/01/31 09:46:50


topological sort能检测loop嘛？我没怎么真正用过topological sort。这题主要就是loop不好处理

不过要考虑success本身就在loop上的情况

最后一题可以想到用强连通分量来做。从source出发找到所有强连通分量，并且判断是否只有success所在的分量有多于一个节点，即图中最多只能有一个包含success在内的环或者没有环。还要检查从source出发是否会抵达出度为0的节点。

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

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

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

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

感謝分享～貓和老鼠感覺好難...

bdhmwzfa 发表于 2019-1-31 16:02
第三轮这个题比较简单的做法，其实是类似cat and mouse那道题，从状态已知的节点出发，倒推其它节点的状态 ...

学习了，回去看看猫和老鼠