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, xy 和 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]为真。

Answer 2

它确实错过了一个案例。

     >x
    /
  >v
 /
r
 \
  >y

0  1  2

在哪里top(r) = 0和top(v) = top(y) = 1。top(x) = 2连接没问题x->y，但top功能必须改变。

我们所知道的是，如果已经有一条路径 fromy到x，那么中间节点的路径top小于x，所以我们可以在遍历时忽略其他节点。