はむ吉(のんびり)の練習ノート

プログラミングとことばに関する話題を中心に,思いついたこと,試してみたこと,学んだことを,覚え書きを兼ねてまとめます.その際に役立った,技術書,参考書,辞書,機器などの紹介も行います.

AtCoder Regular Contest 032 B. 道路工事:複数の解き方と解答例

引き続き、私はAtCoderの過去問を解き進めています。この記事では、その一環として私が取り組んだB: 道路工事 - AtCoder Regular Contest 032 | AtCoderという問題について、それに対するいくつかの解き方と解答例を、学習の記録を兼ねてまとめておきます。

問題の趣旨

単純無向グラフが与えられる。このグラフに辺をx本加えると連結したグラフになるとする。整数xの最小値を求めよ。

方針

求めるものは、与えられたグラフの連結成分の数から1を引いたものです。適当なグラフで実験すれば理解しやすいでしょう。解説のスライドでも述べられているように、連結成分を数え上げる方法としては、深さ優先探索(あるいは幅優先探索)を用いた方法と、Union-Find木を使った方法が挙げられます。

深さ優先探索あるいは幅優先探索による方法

深さ優先探索または幅優先探索を使うと、以下のように連結成分の数を求めることができます。まず、適当な頂点から探索を始めます。次に、それが終わった段階で未訪問である頂点を一つ選び、そこから探索を行います。すべての頂点が訪問済みになるまで、この操作を繰り返します。最初の探索を含めた探索回数の合計が、連結成分の数に一致します。

Union-Find木による方法

Union-Find木はグループ分けを管理するデータ構造です*1。相異なる連結成分を相異なるグループと見立てれば、このデータ構造を用いて本問を解くことができます。具体的には、以下のように行います。まず、頂点u, vを結ぶ辺があるということを、それらが同じ連結成分、すなわちグループに属していると解釈してunionを行います。続いて、木の根である頂点を数えます。すると、その数は与えられたグラフの連結成分の数に等しくなります。

解答例

上記の方針に基づく解答例を以下に示します。なお、いずれのコードでも、頂点の添え字を0始まりに変換していることに注意してください。

深さ優先探索幅優先探索による解答例

まず、深さ優先探索あるいは幅優先探索を使ったコードを載せておきます。いずれのコードでも、与えられた辺の情報を隣接リストに変換してから使用しています。頂点を表す整数をキーとし、それが隣接する頂点を意味する整数を要素にもつ集合を値とするマップで隣接リストを実装しています。これは、初期化の手間を省くためです。

深さ優先探索再帰)を用いた解答コード(Python 3)を以下に示します。再帰を行うため、sys.setrecursionlimitでスタックの最大深度を上げています。

幅優先探索を用いた解答コード(C++11)は次の通りです。

Union-Find木による解答例

Union-Find木を使用したコード(Scala)を以下に載せます。メソッドで最後に評価された値が返り値となることを利用して、returnを省略していることに注意してください。なお、実装はB: Union Find - AtCoder Typical Contest 001 | AtCoderを参考にして行いました。


感想

グラフやそれを処理する基本的なアルゴリズムに慣れてきたのか、すんなりと解くことができました。ただ、グラフに限らず、まだまだ習得できていない技法はたくさんあるので、問題演習を通じて少しずつそれらを学んでいきたいものです。

*1:プログラミングコンテストチャレンジブック』(第2版)p.81