Codeforces Round #544 (Div. 3)F2. Spanning Tree with One Fixed Degree

問題概要

$N$ 頂点 $M$ 辺の単純連結無向グラフが与えられる. ここから適当に辺を削除することでグラフを木にするが, このとき頂点 $1$ の次数がちょうど $D$ になるようにしたい. これは可能か？可能ならば構成例を示せ.

制約

$2 \le N \le 2\times 10^5$
$N-1 \le M \le min(2\times 10^5, N(N-1)/2)$
$1 \le D \le N$

解法

まず, 頂点 $1$ の次数が $D$ 未満なら明らかに構築できません. 以降は次数が $D$ 以上であると考えます.

こういうわけわからん問題があると, 構築できない場合はどういうときか？ということを考えることが多いです. 木を作るうえで, なければならない辺のうち, 頂点 $1$ がかかわっている辺は何個でしょうか？

これは, 頂点 $1$ を除いたグラフについての連結成分の数に等しいです. 頂点 $1$ を除いたときに非連結になるということは, 頂点 $1$ を中間に置かないと各連結成分はそれぞれと連結になれないということです. ですから, $1$ を除いたグラフについての連結成分の数を数えて, それが $D$ 以上かをまず確認しましょう. これを満たしていない場合答えは NO です.

逆に前述の条件を満たしていれば問題のグラフは構築できます. これは, 各連結成分を繋ぐうえで必要な辺を最初に追加した後, $1$ がかかわるその他の辺を次数が $D$ になるまでつないだ後残りのグラフで木を作ればよいです. 頂点 $1$ を中間に置かないと連結にならない部分は最初に連結してしまうので, この方法で木を作成できることがわかります.

実装

実装上は, 頂点 $1$ が各連結成分を繋ぐうえで必要な辺の重みを $0$ , その他の頂点 $1$ がかかわる辺の重みを $1$ , その他の辺の重みを $2$ としたうえで MST をやると楽です.

Submission #145619042 - Codeforces