解説
DFSやBFSというテクニックを使います。 次の記事が参考になると思います。
この問題では、DFSやBFSを用いて、ある都市から通信できる都市に印をつけることで、光ファイバー網で結ばれている都市のかたまりの数を数えることができます。
このようなかたまりを全てつなげるには、 個のかたまりがあるとして
本の光ファイバーが必要となるため、これが答えとなります。
DFSやBFSは、応用範囲も広く、競技プログラミングで最も出てくるアルゴリズムと言っても過言ではありません。
この問題は、特にその中で最も基本的な問題なので、必ず解けるようにしておきましょう。 DFS, BFSの両方で解いてみるのもいいと思います。
