O（n + m）の有向グラフでマザー頂点を見つける方法は？

Question

他のすべての 頂点Gに有向パスで到達できるように、有向グラフの母点G =（V、E）は頂点vです。 O（n + m） Gは母の頂点を含む。 Skienaマニュアル

から

（c）は（N（N + M））方法

Answer 1

Iは実際に答えhereを発見グーグルのみOを発見しました。これが宿題であれば、二度と覗く前に考えなければなりません:)

Answer 2

私は解決策を見ました。私はSCCを見つける必要がないと思う。ランダムな頂点からDFSを実行し、頂点から最後の終了時刻でDFSを実行します。マザー頂点がある場合は、これが必要です。

Answer 3

ステップ1。有向グラフの頂点のトポロジカルソートを行います。

ステップ2。今、私たちは1

ステップ2を実行するには、再びfalseに 配列発見[i]を初期化段階でトポロジー的にソートされた頂点の最初の頂点からすべての頂点に達し、位相幾何学の最初のノードからSTARTIN DFSを行うことができるかどうかをチェックソートされた頂点。

すべての頂点に達すると、グラフにはマザー頂点があり、マザー頂点はトポロジでソートされた頂点の元になります。複雑

時間： STEP1はO(n + m)を取るには、ステップ2はO(n+m) + O(n+m) = O(n+m)

Answer 4

アルゴリズム::

a）は、グラフのDFS/BFSを行い、最後に完成した頂点を追跡するので、合計O(n + m) を取ります'バツ' 。

b）マザー頂点が存在する場合、 'x'がそ​​れらの1つです。頂点 'x'からDFS/BFSを実行して、 'x'がマザーの頂点であるかどうかを確認します。

時間複雑度はO（n + M）+ O（N + M）= O（N + M）