BFS、DFSを利用した問題(アルゴリズム)

Question

上記の問題について、グラフ構造を用いて解こうと試みているのですが、どの部分にBFSやDFSを適用すれば良いか悩んでいます。上手い方針があれば教えていただきたいです。

Answer 1

正答の検証ができないので机上での話になることを了承してください。

まずは与えられたノードを順番に経路探索します。DFSでもBFSでも良いです。ただしスタート地点Sが到着地点の道は無視します。すると複数の独立した有向グラフができるはずです。

任意の有向グラフが閉路ならば、その中の1点からスタートするとその有向グラフ内には必ず到達できるはずです。
閉路でない場合で、到達するための道が存在しないノードが１つある場合、そのノードに道を接続すれば他の有向グラフ内のノードにはすべて到達できるはずです。到達するための道が存在しないノードが複数存在する場合は、それぞれに道を接続しないといけません。

以上のことにより、ある独立した有向グラフにおいて頂点Sからすべての町に到達するために新たに作る必要がある道の数は、max(1,到達するための道が存在しないノードの数)となります。

これを存在するすべての独立した有向グラフごとに積算すれば答えとなるはずです。