DRW 最新OA 挂经

倒序浏览 · 2022-7-30 10:10:04

DRW 最新OA

3道题，限时2小时30分钟，发过来后3天内做完

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

thm, 这个算法彻底没学过完全不知道是啥，直接挂

bydstand

出度为0的点是否唯一？

ALEXJI19991007

罗马城那道题难道不是DFS就行了么？

匿名用户-4HVTJ *2022-7-30 13:07:58* · 2022-7-30 13:07:58

ALEXJI19991007 发表于 2022-7-30 00:00
罗马城那道题难道不是DFS就行了么？

你说的是从每一个起点DFS 找共同点吗？那样的话O(v^2)，一共有200000个v 肯定不行，找strongly connected node 需要用 tarjan's algorithm, O(v) time

匿名用户-4HVTJ *2022-7-31 02:12:45* · 2022-7-31 02:12:45

Rome 出度不一定为0，但是却是从所有其他node strongly connected，这个点时唯一的

小亩_883c82e

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

匿名用户-YME8F *2022-8-3 13:03:46* · 2022-8-3 13:03:46

楼主这是什么岗的OA？

isabuster1127

小亩_883c82e 发表于 2022-7-31 11:11
我也感觉rome就只是出度为0呀，感觉直接找好像就可以了。因为他说了是个connected graph且有N条边，所以没 ...

我也是这么做的，不知道对不对，因为这个图一定是一个tree就简单很多了

cscsis

我也是想了好半天罗马城那道题，最后还是从出度的角度遍历一遍搞定，总觉得怪怪的，因为根本没用上第二个数组也就是入度。