Kazun の競プロ記録

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

AtCoder Beginner Contest 288 C問題 Don’t be cycle

AtCoder ABC288 ABC 300 pts C問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 頂点 $M$ 辺の単純無向グラフ $G=(V,E)$ が与えられる. ただし,

$V:=\{1,2, \dots, N\}$
$E:=\{A_j B_j \mid j=1,2, \dots, M\}$

このとき, $G$ のサイクルを持たないような全域部分グラフ $H=(V,F)$ における $\#(E \setminus F)$ の最小値を求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq M \leq 2 \times 10^5$
$1 \leq A_j, B_j \leq N$

解法

$\#(E \setminus F)$ の最小値を考えるということは $\# F$ の最大値を考えることに対応する. よって, サイクルを持たない全域部分グラフにおける辺の本数の最大値を求めることにする.

実は, 辺の本数の最大値は $G$ の連結成分の数を $K$ として, $N-K$ である.

これを示すためには次の事実を使う.

$n$ 頂点の木における辺の本数は $(n-1)$ である.

まず, $G$ の連結成分の数が $K$ であるから, 各連結成分における全域木を考えることによって, 辺の本数 $(N-K)$ を達成できる.

一方で, $H=(V,F)$ がサイクルを持たないとする. このとき, $H$ の各連結成分は木であり, $H$ は $G$ の部分グラフなので, $G$ の連結成分の数 $K'$ は $K' \leq K$ を満たす. よって, $\# F=N-K' \leq N-K$ となる.

よって, $\# F$ の最大値は $N-K$ であるから, 求めるべき $\#(E \setminus F)$ の最大値は $M-(N-K)$ である.