Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 239 F問題 Construct Highway

AtCoder ABC ABC239 F問題 500 pts

問題

提出解答

問題の概要

$N$ 頂点 $M (\leq N-1)$ 辺のグラフ $G=(V=[\![N] \! ], E=\{A_j B_j \mid 1 \leq j \leq M\})$ が与えられる. 以下を満たすような拡大グラフ $H=(V,F)$ は存在するか? 存在するならば条件を満たす $H=(V,F)$ における $F \setminus E$ の一例を求めよ.

$H$ はサイズ (辺の数) が $N-1$ の連結グラフ
$v=1,2, \dots, N$ に対して, $\operatorname{deg}_H(v)=D_v$ である.

制約

$2 \leq N \leq 2 \times 10^5$
$0 \leq M \leq N-1$
$1 \leq D_v \leq N-1$
$1 \leq A_j \lt B_j \leq N$
$j \neq j' \Rightarrow (A_j, B_j) \neq (A_{j'}, B_{j'})$

解法

条件を満たす $H$ は木である. このことも合わせて, 以下のいずれかに該当する場合は直ちに否定的に結論づけることになる.

$\displaystyle \sum_{v=1}^N D_v \neq 2(N-1)$ (握手補題より)
$\exists v \in V {\rm s.t.} \operatorname{deg}_G(v) \gt D_v$
$G$ が森ではない (つまり, サイクルが存在する).

以下のようなアルゴリズムによってできた拡大グラフ $H$ が条件を満たすかどうかで判定でき, 肯定的であるときは $H$ がそのまま一例になる.

$H \gets G$
次数が不足している頂点が存在するの連結成分の数が以上である限り, 以下を実行する.
- 不足している次数の総和が1番目, 2番目に大きい連結成分 $C,D$ を取る (仮定から総和は共に正である).
- $C,D$ からそれぞれ不足している頂点 $x,y$ を選び, $H$ に辺 $xy$ を加える.

辺を加え, 連結成分をまとめる際に次数が不足している頂点についての情報を統合する必要があるが, マージテクを利用することにより, 計算量 $O(N \log N)$ で判定できる.