algorithm - 会聚迷宫 : Largest cycle

Question

这个问题是在一次采访中被问到的，我仍在寻找最佳解决方案。

给你一个有 N 个单元格的迷宫。每个单元格可以有多个入口点，但导出点不能超过一个(即入口/导出点是单向门，如阀门)。

单元格以从 0 开始的整数值命名到 N-1。

您需要找到迷宫中最大环的长度。如果没有循环，则返回 -1。

输入格式

• 第一行有N个单元格
• 第二行列出了 edge[] 数组的 N 个值。 edge[i] 包含的单元格编号可以一步从单元格“i”到达。如果第 i 个单元格没有导出，则 edge[i] 为 -1。

输出格式

• 最大周期的长度。

示例输入:

23

4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21

示例输出

6

我已经尝试使用 DFS 来执行此操作以查找所有可能的循环并打印最大的循环大小。如果有更好的解决方案，请告诉我。

Answer 1

给定图中的一个节点，从它开始有一条唯一的最大路径(因为从任何节点最多有一个导出)。它可能循环也可能不循环。

很容易找到从一个节点开始的最终循环长度:继续跟随导出节点，记录沿路径集合中的节点。当您找不到导出节点或您将要访问以前访问过的节点时停止。如果没有导出节点就没有循环，否则你可以从以前访问过的节点开始找到循环长度，然后重新跟踪循环。 [您也可以在这里使用 Floyd 算法，它需要 O(1) 而不是 O(N) 存储，但我们将在下一步中使用 O(N) 存储]。

使用它，可以在 O(N) 时间内找到最大循环:对图中的每个节点重复上述算法，但缓存结果(如果没有找到循环则存储 -1)。如果你在你的路径上找到一个先前缓存的结果，你必须小心停止上面的循环查找，并且一旦你找到一个节点的结果，你必须缓存路径上所有节点的结果，直到找到一个结果的节点已经缓存。最大循环的大小就是最大缓存值的值。

这是 O(N) 运行时间:图中的每条边(其中最多有 N 条)最多被跟踪 3 次，并且缓存为图中的每个节点恰好更新一次。它使用 O(N) 额外的存储空间。