微软on campus跪经

白板，给一个有向图， 找出所有能够访问到图中其他所有节点的节点。

标准做法应该是每个点DF

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

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

"0" alt="" />move on了，求人品

mother node的定义是可以沿有向图到达所有其他node，这题问的其实就是找出所有的mother node。这样的话，先找到一个mother node，然后通过反转DFS来找谁能到达这个mother node，根据原理，能够到达这个mother node的node必然也是一个mother node（因为它可以先走到这个mother node然后通向所有node），到不了这个mother node的node必然不是mother node。

找mother node的线性解：
https://www.geeksforgeeks.org/find-a-mother-vertex-in-a-graph/

反转用到的地方比较广泛，不过按我目前的知识一般是在找node和测node的connectivity的时候用

可以先用O(V+E)找能通向所有node的mother node，然后把图里所有edge反转，从mother node出发BFS或DFS，把沿途所有发现的node都加进答案集。线性复杂度

图是什么形式给的啊？

每个点dfs应该可以 不过感觉复杂度有点高啊 这个图有环吗？

请问投的是什么岗位啊？new grad是统一投swe还是按组投呢

应该是校友吧~请问是前几周那个info session聊简历拿的oci吗？
希望后面还能有机会

如果A能到所有点，如果B能到A，那A也可以到所有点，是不是可以存个能到所有点的点的Set，然后在DFS到一个点时候，检查一下到的点在不在Set里，这样能稍稍优化一下。
比如A能到所有点，B只有一个链接到A，B只需要检查一次就好了。
这个想法适用于有环的图==
但BigO复杂度还是一样。

补充内容 (2018-9-11 16:11):
开头打错了，如果A能到所有点，如果B能到A，那B也可以到所有点

Topological Sorting?

补充内容 (2018-9-12 11:11):
oooo又读了一遍才发现楼主这个题要找的不只一个点.... 我去重新看QAQ

补充内容 (2018-9-12 12:12):
这个题意思是不是要想成strongly connected components，如果有node满足这个条件  互相是strongly connected

hqx346 发表于 2018-9-12 10:29
Topological Sorting?

如果拓扑排序的话按什么排序呢？

xuca9220 发表于 2018-9-12 07:10
如果A能到所有点，如果B能到A，那A也可以到所有点，是不是可以存个能到所有点的点的Set，然后在DFS到一个点 ...

a能到所有的点，那么有路径a->b，b又可以到a说明有路径b->a。
那不就成环了？

Kosaraju’s算法了解一下