融合迷宫:最大的循环

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)额外的存储空间.