只想安静的狗带的airbnb面试

木易wen · 2016-11-12 05:26:10

梦醒的我发表于 2016-11-12 05:20
有环不行，比如1->2->1

可以先用topo的方法遍历一遍，然后找到所有入度为0的。如果最后有环并且这个环没有被遍历过就拿出其中一个点来当入口

木易wen · 2016-11-12 05:48:52

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

木易wen · 2016-11-12 07:10:47

这样有个问题就是可能第3步里面的点可能在不是环上的点，比如1->2->3->1->4,如果把4加到res里就多余了，而且不能遍历该带环图

Travianfood · 2016-11-12 07:39:21

第一题我没误解的话不是经典题吗？先对整个graph做SCC，然后会得到一个topological graph，然后就直接把根选下去就行啦~

twfx1123 · 2016-11-12 07:59:18

Travianfood 发表于 2016-11-11 15:39
第一题我没误解的话不是经典题吗？先对整个graph做SCC，然后会得到一个topological graph，然后就直接把根 ...

SCC是strongly connected components?

some3411 · 2016-11-12 08:29:48

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

some3411 · 2016-11-12 08:34:22

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

	51垅无效楼层，该帖已经被删除

	53垅无效楼层，该帖已经被删除

	55垅无效楼层，该帖已经被删除