AtCoder Regular Contest 037 B. バウムテスト：解き方とPython 3による解答例

最近、私は主にAtCoderやyukicoderの問題を少しずつ解いています。この記事では、今日私が解いたB: バウムテスト - AtCoder Regular Contest 037 | AtCoderという問題の解き方およびPython 3の解答例を、学習の記録を兼ねてまとめておきます。

問題の趣旨

入力として、N個の頂点とM本の辺からなる無向グラフが与えられる。その連結成分のうち木であるもの、つまり閉路をもたないものの個数を出力せよ。

方針

解説のスライドで述べられているように、探索により連結成分を列挙し、その過程で各連結成分に閉路があるか判定すればよいでしょう。スライドでは深さ優先探索を繰り返すという方法について述べられていますが、以下のコードに示したように幅優先探索を繰り返しても差し支えはないようです。

幅優先探索を用いる場合に、各連結成分について閉路の有無を判定する方法について大まかに述べます。幅優先探索ではキューから頂点uを取り出し、それに隣接する頂点vが訪問済みかを確認します。このステップで、次の2条件をあるu, vが同時に満たせば、その連結成分は閉路をもつ（i.e. 木ではない）ことがわかります。そのようなu, vが全くなければ、その連結成分には閉路がないことになります。

1. 頂点vが訪問済みである
   • 各頂点が訪問済みかを記録する配列（visited[]とする）を使って判定できる
2. 幅優先探索順序で頂点uの一つ前に訪問した頂点がv以外である
   • 各頂点の一つ前に訪ねた頂点を記録する配列（pred[]とする）を使って判定できる

所与のグラフは無向グラフであるため、v→u→vという探索順がありうることに注意してください。この場合には、連結成分に閉路が存在しなくても、vを2回訪問しようとすることがあります。これを考慮して、第2の条件を加えています。解説のスライドにある「直前に訪れた頂点を覚えておかないと、誤検知してしまう」という記述は、この点についてのものであるといえます。

解答例

上記の方針に従って書いたPython 3によるコードを、以下に示します。初期化の手間を省くため、配列の代わりにPython標準ライブラリのcollections.defaultdictを用いています。

感想

問題演習を重ねていくうちに、幅優先探索や深さ優先探索をはじめとする基本的な探索が馴染みのあるものになってきました。この問題を通じて、配列pred[]の使い道がわかりかけてきたような気がします。