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

How to tell if adding an edge to a DAG forms a directed cycle?

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

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

它确实漏掉了一个案例。

     >x
    /
  >v
 /
r
 \
  >y

0  1  2

其中 top(r) = 0top(v) = top(y) = 1 以及 top(x) = 2。连接x->y还好,但是top功能要改

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

我们可以利用 |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] 为真。