阻止仙人掌图上的有向路径[关闭]

我想找到最长的路径距离仙人掌图具有某些阻塞定向路径。

For example, if we have following 4 nodes,

这意味着

• 如果我们访问 1，我们就无法访问 2 也就是说，1 -> 2 和 1 -> 3 -> 2 是不允许的。 然而，2 -> 1 是允许的。

Likewise

• 无法从 2 前往 3

• 无法从 3 前往 1

• 无法从 1 到 0

• 可以旅行任何其他人

所以我们有路径 (1, 3, 2), (0, 2, 1) 等。因此最长距离是 3。

在本例中，答案是 9。（4, 5, 6, 7, 8, 0, 9, 2, 3）等...

我被这个问题困扰了一个星期。尽管如此，我还是不知道如何处理。谢谢。

听起来你所拥有的只是一个有向图，但方向与箭头所示相反。反转方向并运行标准最长路径图算法。

https://en.wikipedia.org/wiki/Longest_path_problem

据我了解，允许的路径是（但你不能走其他路）：

0 => 1
1 => 3
3 => 2
2 => 1

将它们转换为有向图并对其运行最长路径算法。

编辑：更新答案以反映最长路径而不是最短路径