2007JOI春合宿Day4-1 Fiber 解説

問題リンク

解説

DFSやBFSというテクニックを使います。 次の記事が参考になると思います。

• けんちょんさんの記事
• けんちょんさんの記事2
• kaageの記事

この問題では、DFSやBFSを用いて、ある都市から通信できる都市に印をつけることで、光ファイバー網で結ばれている都市のかたまりの数を数えることができます。 このようなかたまりを全てつなげるには、 個のかたまりがあるとして 本の光ファイバーが必要となるため、これが答えとなります。

DFSやBFSは、応用範囲も広く、競技プログラミングで最も出てくるアルゴリズムと言っても過言ではありません。

この問題は、特にその中で最も基本的な問題なので、必ず解けるようにしておきましょう。 DFS, BFSの両方で解いてみるのもいいと思います。