algorithm - 如何检测有向图中循环中的循环

Question

我最近在 amazon 面试中遇到了一个问题，想知道 stack overflow 对这个问题的看法。

问题是

输入:由邻接表表示的有向图

需要的输出:此图是否有一个循环中的一个循环，如果有，这些循环是什么。循环条件中的循环定义如下:图中有2个循环C1和C2，它们都共享一条或多条边，则称它们为循环中的循环。

例子如下:

在上图中可以看到有 2 个循环 C->D->E->F->G->H->C 和另一个表示为 H->I->J->G-> 的循环H .. 我们可以看到这 2 个循环将边 G->H 作为共享边，因此我们可以将它们称为循环中的循环。

So tha answer will be yes there are cycles in a cycles and
 the cyles are  C->D->E->F->G->H->C and H->I->J->G->H

我在采访中的方法是检测所有循环(通过 DFS 遍历)，一旦检测到，就在散列映射中维护那里的边缘。然后当找到另一个循环时，我再次将它们插入 hash 。这被礼貌地拒绝了，他在采访中更进一步，没有进一步讨论。然后我认为找到所有循环是一个难题。我很困惑 。有人可以澄清一下吗？

Answer 1

1. 找到所有循环
2. 检查每对循环的边缘之间的非空交点(如果交点不为空，则两个循环是一个循环中的一个循环)