📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: henear
跳转到指定楼层
上一主题 下一主题
收起左侧

G挂

🔗
杨超越 2019-2-4 10:07:25 | 只看该作者
全局:
第一问可以UF?第二问就是一个BFS搜索?对于A的每一个直接相连的node,做一次bfs,然后看看那些点会因为这一条路径被cut而使得抵达他们的path减少,如果变为0 那么这条路径被cut后没法接到消息的node个数+1?
回复

使用道具 举报

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

使用道具 举报

🔗
 楼主| henear 2019-2-4 11:20:55 | 只看该作者
全局:
jackalsin 发表于 2019-2-4 08:57
楼主,能问一下A一定是消息源么?

嗯……一定有且只有一个信息源。
你可以定为A,也可以定为B……啥名都行,我跟面试官讨论了下他说你定吧。于是我就定A了。
//感觉这个细节和题没啥关系
回复

使用道具 举报

🔗
 楼主| henear 2019-2-4 11:22:38 | 只看该作者
全局:
xh_pku 发表于 2019-2-4 08:29
这题我觉得,假设A的neighbor 为集合nA,先把所有有两条路径的节点全部去掉,然后在看单独通过nA中每个节点 ...

为啥是把有2条路径的都去掉,我觉得是≥2条吧……
回复

使用道具 举报

🔗
 楼主| henear 2019-2-4 11:24:04 | 只看该作者
全局:
杨超越 发表于 2019-2-4 10:03
不好意思 我没明白“如果每个人至多从一个人那里得到消息” 这是什么意思。。这个限制条件有和没有有什么区 ...

感觉也没啥特别多,就是图与树的区别
回复

使用道具 举报

🔗
henryqcy 2019-2-4 11:44:18 | 只看该作者
全局:
杨超越 发表于 2019-2-4 10:03
不好意思 我没明白“如果每个人至多从一个人那里得到消息” 这是什么意思。。这个限制条件有和没有有什么区 ...

同问。。。。。。
回复

使用道具 举报

全局:
henear 发表于 2019/02/04 11:22:38


为啥是把有2条路径的都去掉,我觉得是≥2条吧……

对的 我说错了
回复

使用道具 举报

🔗
杨超越 2019-2-4 13:21:22 | 只看该作者
全局:
第二问我觉得可以DFS,只要那个节点的indegree > 1 就可以直接返回,因为说明肯定有其他的path能够传递信息到这个节点。统计一下A到某个直接子节点这条path断掉后 会让多少个node的indegree 变成0 ,选最大的那个?
回复

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

本版积分规则

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