楼主: TonyLic
跳转到指定楼层
上一主题 下一主题
收起左侧

Google NYC onsite 感受分享

🔗
 楼主| TonyLic 2016-9-18 05:52:56 | 只看该作者
全局:
william_gong 发表于 2016-9-17 08:58
directed map怎么判断连通 求On解法

随便选一个点,DFS,如果是连通的,翻转每条路径,再次从这个点DFS,如果还是连通的,那原来整个图是连通的
这是一个比较经典的算法,没看过还是挺难想到的
回复

使用道具 举报

🔗
william_gong 2016-9-18 06:30:18 | 只看该作者
全局:
TonyLic 发表于 2016-9-18 05:52
随便选一个点,DFS,如果是连通的,翻转每条路径,再次从这个点DFS,如果还是连通的,那原来整个图是连通 ...

确实是经典算法。。全忘了。。
回复

使用道具 举报

🔗
wugoat 2016-9-24 06:05:55 | 只看该作者
全局:
祝楼主好运 请问undirected map 是啥 graph?
回复

使用道具 举报

🔗
wugoat 2016-9-24 06:08:06 | 只看该作者
全局:
面试官有说这里的directed graph是DAG吗
回复

使用道具 举报

🔗
wugoat 2016-9-24 06:10:09 | 只看该作者
本楼:
全局:
应该不是
回复

使用道具 举报

🔗
wugoat 2016-9-24 06:10:28 | 只看该作者
本楼:
全局:
应该不是
回复

使用道具 举报

🔗
wugoat 2016-9-24 06:12:11 | 只看该作者
本楼:
全局:
应该不是
回复

使用道具 举报

🔗
 楼主| TonyLic 2016-9-30 07:29:39 | 只看该作者
全局:
wugoat 发表于 2016-9-24 06:05
祝楼主好运 请问undirected map 是啥 graph?

typo..
就是undirected graph
另外没说是否有环
回复

使用道具 举报

🔗
virpro 2016-10-8 09:49:25 | 只看该作者
全局:
TonyLic 发表于 2016-9-18 05:52
随便选一个点,DFS,如果是连通的,翻转每条路径,再次从这个点DFS,如果还是连通的,那原来整个图是连通 ...

赞,这个思路好牛逼
回复

使用道具 举报

🔗
bcc 2016-10-8 23:50:21 | 只看该作者
全局:
family tree 是common ancestor么
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表