DAGにエッジを追加すると指示サイクルが形成されるかどうかを確認するにはどうすればよいですか？

Question

グラフの各頂点vに対してDAGと与えられたトポロジカルな次数関数を持つと仮定すると、2つの特定のノードを見ると、x、yはそれを知っています| top（x）-top（y）| < 10エッジx-> yを追加するとグラフにサイクルが形成されるかどうかを確認するにはどうすればよいですか？ 私は、O（V + E）より良い解決策を達成しようとしています...

私が考えていたのは、top（x）> top（y）サイクル。 しかし、私は事件を逃すかもしれないのだろうか、また、トップ（x）のトップ（y）| < 10私には何か追加情報がありますか？どんな啓蒙ですか？

Answer 1

|top(x) < top(y)| < 10という事実を利用して効率的な解決法を見つけることができます。

最初に、top(x) < top(y)にはサイクルがないことに注意してください。それ以外の場合は、ar[] = y, z₁, z₂ … z_k, xをyとxのトポロジカルソートのノードとします。 yからxまでのパスがある場合、これらの頂点を経由することしかできません。 yからのパスがあり

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 

X IFF 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関数を変更する必要があります。私たちが知っている何

はyからxにすでにパスがあります場合は、中間ノードはtop少ないxより年代を持っている、ということですので、私たちは横断しながら、他のノードを無視することができます。