街を頂点、高速道路を辺としたグラフを考えます。問題は、「指定された辺を全て含み、各頂点の次数が指定された値になるような木を構築せよ」となります。

\(\sum D_i\neq 2N-2\) であるとき条件を満たすことは明らかに不可能です。\(\sum D_i= 2N-2\) である場合を考えます。

まずは条件を満たすことが可能かどうか考えてみましょう。

最終的なグラフは木になるので、既存の辺により同じ連結成分に属している頂点の間に新たに辺が張られることはありません。したがって、次数の不足は連結成分ごとにまとめて考えてよいことがわかります。各連結成分について、その連結成分に属する頂点たちの次数の不足の合計が \(n\) であることを「次数が \(n\) 足りない」などと表現することにします。

実は、条件を満たすことが可能ならば、次のようなアルゴリズムで構築可能です。

• まず、以下の操作を可能な限り繰り返す：次数が \(1\) 足りない連結成分 \(X\) と、次数が \(2\) 以上足りない連結成分 \(Y\) を任意に選び、これらの間に辺を張る
• 上の操作が不可能になった時点で、連結成分がちょうど \(2\) つ残っており、そのどちらも次数が \(1\) 足りないとき、それらの間に辺を張る。そうでないとき、条件を満たすことは不可能

構築パートは上記アルゴリズムに基づいて、各連結成分で次数が不足している頂点たちの配列をもっておき、連結成分の次数の不足が \(1\) か \(2\) 以上かで分けておくことで処理できます。

実装例(C++)