如何在有向图中检测循环中的循环

Question

我最近在亚马逊面试中遇到了一个问题，并想知道stackoverflow对此的看法。

问题如下：

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

所需输出：此图是否具有循环，并且如果是，则这些循环是什么。 循环中的循环条件定义如下：图中存在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遍历检测所有的循环，并一旦检测到就在哈希映射中维护它们的边缘。然后当发现另一个循环时，我再次将它们推入哈希表中。但这种方法被礼貌地拒绝了，他没有进一步讨论就继续面试下去了。之后我意识到找到所有的循环是一个难题，让我感到困惑。请问有人可以澄清吗？

- MAG

---

首先被要求实现一个基本的循环检测，我使用深度优先搜索方法编写了代码，他对此感到满意。 - MAG

有关图论的标准书籍包括在图形中检测环的算法。 - MWiesner

如果我无法表达问题，我很抱歉。所需的输出是：这个图中是否有一个循环，并且如果有，那么这些循环是什么。我已经更新了他想要的结果答案的问题。 - MAG

Answer 1

1. 查找所有循环
2. 检查每对循环的边之间是否存在非空交集（如果交集不为空，则两个循环是一个循环中的循环）

- MrSmith42