电面第二轮

国人小哥给了个有向图找环，只不过每个点可以有多条路径，题目不难 属于考察基本功，但无奈我的基本功有点渣实，第一把dfs 暴力写的有点小错，一直没改出来，小哥提示了一下改对，
分析

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

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

看来是基本功有点渣，希望后面的面试有所进步吧，，

目前拒信还没到，不过估计也快了

freakpao 发表于 2021-12-6 00:10
哦 我傻了 明显不行， 多个node到1个不work  请忽略

DFS是可以的，甚至可以找出强连通分量。只不过dfs时要维护更多的metadata
https://www.geeksforgeeks.org/ta ... nnected-components/

shawnchangsdu 发表于 2021-11-18 16:30
请问每个点可以有多条路径是什么特殊条件？
即使是有向图的话
一个节点也都是可能会有多条边的吧？

没什么特殊条件，就是有向图多条边找环。。。
A [B,C,D]
B [C, D]
D [A]

freakpao 发表于 2021-12-5 21:01
有向图dfs + visited 就行吧？ 重复visited就是有环，不需要拓扑吧 还是我对有向图的环理解有出入？

哦 我傻了 明显不行， 多个node到1个不work  请忽略

每个点可以有多条路径是指一个node可以指向多个node么

langjianke87 发表于 2021-11-17 17:14
每个点可以有多条路径是指一个node可以指向多个node么

是的

这个是可以用拓扑排序做吗？

ntp8 发表于 2021-11-17 20:51
这个是可以用拓扑排序做吗？

都可以吧 比较多方法都行，

请问每个点可以有多条路径是什么特殊条件？
即使是有向图的话
一个节点也都是可能会有多条边的吧？

这题的考点应该就是拓扑排序了，我之前也被问到了类似的。

请问这个题判断有没有环还是要把所有环打印出来？

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

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