algorithm - 如何判断向 DAG 中添加边是否形成有向循环？

Question

假设我有一个 DAG 和图中每个顶点 v 的给定拓扑顺序函数，当查看 2 个特定节点时:x，y 我知道 |top(x)-top(y)|<10 如何我可以判断添加边 x->y 是否会在图中形成一个循环吗？ 我正在尝试实现比 O(V+E) 更好的解决方案...

我的想法是检查是否 top(x) > top (y)，如果是，那么我们创建了一个循环。 但恐怕我可能会错过一个案例，而且 |top(x)-top(y)|<10 是否给我任何其他信息？有什么启示？

Answer 1

我们可以利用 |top(x) < top(y)| < 10 的事实找到有效的解决方案。

首先，请注意如果top(x) < top(y)没有循环。否则，让 ar[] = y, z₁, z₂ … z_k, x是 y 和 x 之间拓扑排序中的节点。如果存在一条从y到x的路径，它只能经过这些顶点。所以只需检查是否有路径:

haspath[] = {false}
haspath[1] = true
for i = 2 to k+2
  for j = 1 to i-1
    if haspath[j]==true and edge(ar[j],ar[i])
      haspath[i] = true
      break

存在一条从 y 到 x 的路径当且仅当 haspath[k+2]是真的。