練習問題１ 回答

[id:lethevert:20070108:p1]

1.

一般性を失うことなくグラフが連結であると言えるとしてから、帰納法。

2.

時間計算量を考えなければ簡単。
リンクを１つずつたどりながら、新しいノードが以前に出現していないかを毎回もう一度頭からたどり直して確認することで、最初に以前に出現したノードが再度出現したところで、終了。O(N^2)かな？
この線で効率を改善するなら、適当なサイズの配列を用意して、新しいノードが見つかるごとにノードのハッシュ値のインデックスに対応する要素に、そのノードへのリンクを持って（衝突したら、先にあったほうを残す）、出現チェックにそのハッシュテーブルを利用する。ベストケースでは、O(N)になる？

3.

2.が解けたら単純。
先に一方のノードを2.の方式で循環が確認できるところまでたどって、そのあと、もう一方のノードから循環が確認できるところまでたどりながら、最初の方で確認したノードが出現するかを確認する。計算量は、2.と同じ。