IndiaHacks 2016 - Online Edition E. Bear and Forgotten Tree 2

本番は嘘解法で通した。

グラフが補グラフの形で与えられる。このグラフの辺をいくつか使って頂点 0 の次数が K であるような木を作ることができるだろうか。

頂点 0 に繋げられる頂点をすべて繋げて木を作る。もし頂点 0 の次数が K 未満なら構成不可能。

頂点 0 の次数が K より大きいときは次数が K になるまで頂点を切り離す。

単に切り離すと連結でなくなってしまうので、別の部分木に繋ぐ必要がある。

f:id:pekempey:20160321164228p:plain

次数が K になるまで頂点を切り離すことを考えるよりは、頂点をできるだけ切り離して次数が K 以下になるかを見た方がやりやすい。

なぜなら、できるだけ切り離した後の頂点 0 の次数は、頂点 0 を取り除いたグラフの連結成分の個数に対応するからである。

ただし、これは与えられたグラフが連結の場合の話なので、グラフが連結であるかどうかの判定も別に考える必要がある。

補グラフの連結成分の求め方は、次の問題の解説を探すと見つかる。

まだ訪れていない頂点を set で管理して DFS したとき、遷移に失敗する回数は O(m) 回で抑えられるということを使う。

本番中に提出したコードでは連結成分を求めるパートをごまかしていたのだが、テストケースが弱かったおかげで通すことができた。