sharir kosarajuアルゴリズムをDirectedグラフで実行してみましょう。そして、このグラフには円弧（u、v）があります。 このアルゴリズムでは、2つのDFSパスがあります。 ここで、頂点uを最初の深さツリーTに挿入するとします。 vをどこに表示できますか？以前に作成された別のツリーか、それとも後で作成されたツリーですか？ ありがとうございます！sharir kosarajuアルゴリズムと頂点
私はテストのために学習しています...これは私が推測する宿題のようなものですが、実際には手がかりはありません！
Kosaraju's Algorithmは、グラフの転置が元のグラフと同じ数の強連結成分（SCC）を有するという事実に基づいている。
1）あなたはSはG内のすべてのノードが含まれていませんが、グラフGと空のスタックS.
2）は、ランダム頂点uを選択し、uの上でDFSを行うことがあります。このDFSの間にノードvを探索したら、ノードvをSに押し込みます。
質問に戻ると、有向枝（u、v）がある場合、vは必ずスタックSに挿入されますu。しかし、vの挿入とuの挿入の間には、より多くのノードが存在する可能性があります。
3）Transpose of Gは、スタックSから頂点をポップして、Sが空になるまで実行します。これは、グラフGのすべてのSCCを取得します。
wiki：http://en.wikipedia.org/wiki/Kosaraju%27s_algorithmはかなり有益です。私はアルゴリズムを実装しており、ここで利用可能です。
http://khanna111.com/wordPressBlog/2012/04/11/strongly-connected-components-of-a-graph/
理解するための主なものは、合格後の最初のステップではスタックの最上位の要素が親になることであり、それは第二段階で彼らが早く飛び出しされるだろうと転置を操作します元のグラフで強く接続されたノードは、転置で強く接続されたままです。
最初の合格の理由は、両親をスタックの一番上に置くことです。
それでは、どうしてうまくいかなかったのですか？確かにあなたはそれが2つの連続したDFSパスを実行することができるはずですか？だから、少なくともあなたが解決しようとする問題の一部があり、あなたがそこから立ち往生したら、より具体的な質問をすることができます –