1. ホーム
  2. 質問と答え
  3. あるSCCから別のSCCへのパスが存在するかどうかを調べるにはどうすればよいですか？

あるSCCから別のSCCへのパスが存在するかどうかを調べるにはどうすればよいですか？

2017-11-04 9 views
0

グラフでは、強く接続されたコンポーネントを見つけた後、相互にパスを持つSCCの数をどのように見つけることができますか？私は、SCC1からSCC2への道があるかどうかを知りたい。あるSCCから別のSCCへのパスが存在するかどうかを調べるにはどうすればよいですか？

出典

2017-11-04 AryaStark

+1

あなたの試みとなぜあなたはそれが問題だと思いますが何ですか？実際、答えは私には明らかです。 – ram

+0

私のアプローチは、SCC1の頂点でDFSを実行することです。問題のあることがわかったのは、すべてのSCCが互いのパスを持っているわけではないからです。そして、もし私が最初に始めるならば、私はSCCの最大数に到達する方法を知りたいと思います。 – AryaStark

+0

ちょうどそれを確認する：それは有向グラフですか？もしそうなら、2つのSCCが接続されているとはどういう意味ですか？彼らはお互いに到達できる必要がありますか？ – ram

答えて

0

あなたは二つのことを尋ねた：

お互いへのパスを持っているのSCCの数を見つけるのですか？

すべてのSCCからdfsを実行し、到達可能なSCCを保存できます。

例：SCC Aからdfsを実行し、SCC BおよびCにアクセスできます（訪問しているノードのSCCが何であるかを確認してください） 次に、別のSCC Dからdfsを実行し、SCC A.現在、他のものが何であるかを計算しているので、dfsを停止することができます。あなたが唯一のSCCは、（真/偽）他から到達可能であるかどうか、あなたは各SCCの中にIDを割り当てることができますに知る必要があると仮定すると

だから、時間の複雑さはO（N + M）である

出典

2017-11-05 00:06:51

関連する問題

 関連する問題