頂点のセットが強く接続されたコンポーネントの一部である場合、コンポーネント内のすべての頂点が互いに到達できることを理解しています。サイクル。強固に接続されたコンポーネントをサイクル検出として使用する
ここで、グラフG =（V、E）にサイクルがある場合、そのサイクルはscc内になければならないと主張しています。
つまり、すべてのサイクルはsccの一部でなければなりません（私の主張）。
私はどのような反例も私の主張には考えられないので、グラフにsccの一部ではないサイクルがあるかどうかを知りたいと思います。
または 私の主張は正しいですか？
eは=（u、v）が問題になっているエッジとすると述べました。 Gがeを含むサイクルは、Gが{e}のvに接続されている場合にのみ、 であることに注意してください。 私たちのアルゴリズムは、単にG {e}上のuからDFSを実行し、vがu から到達可能であればyesを出力し、それ以外の場合は出力しません。 このアルゴリズムは、DFSが線形時間で実行されるときに線形時間で実行されます（そして、uを含むコンポーネントを見つけるDFSアルゴリズム の一部のみを実行します）。このアルゴリズムは明らかに正しいです。 もしuがある経路pによってG {e}のvに接続されていれば、pにエッジeを加えてサイクルを形成することができます。 それ以外の場合は、Gからeを削除するとuとvが切断されます。
正しいです。 1組の頂点が1つのサイクル内にある場合、これらの頂点はすべて（サイクルを巡って）互いに到達可能であるため、定義上SCCです。
は、それが正確にプログラミングの問題ではない、ということ:)
ありがとうございます。まあ、私はそれがSCCなら、それはサイクルであることを知っています。しかし、私は、SCC algoがグラフ内のすべてのサイクルをキャプチャするのか、あるいは少数の選択しかないのかを尋ねています。あなたがドイツのシェパードなら、あなたは犬です。しかし、あなたが犬なら、それはあなたがドイツのシェパードであることを意味しません。私の類推 – antz
私の答えは正確に言われました：頂点のセットが1つのサイクルにある場合、それらはSCCにあります。あなたが求めていたものではありませんか？どのように私はそれを言うことができますか？ – rici
いいえ、あなたは正しいです。 「一連の頂点が1つのサイクル内にある場合、その頂点はSCC内にあります。 （特異な）。グラフ内のすべてのサイクルがSCCであることを確認したかったのは、「頂点のセットが1つのサイクル内にある場合、それらはSCCにあります」。私はそれがサイクルであるがSCCによって捕らえられない場合があるのだろうかと思っていた。あなたは誰もいないと言っています。大丈夫ありがとう！何が必要なのですか？ – antz