Kazun の競プロ記録

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

AtCoder Beginner Contest 229 E 問題 Graph Destruction

AtCoder ABC ABC229 E問題 500 pts

問題

提出解答

問題の概要

$V=\{1,2,\dots,N\}, E=\{A_1 B_1, \dots, A_MB_M\}$ とする. グラフ $G=(V,E)$ に対して, $k=1,2, \dots, N$ に対して, 以下を求めよ.

$G-\{1,2,\dots,k\}$ の連結成分の個数

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq M \leq \min \left(\dfrac{N(N-1)}{2}, 2 \times 10^5 \right)$
$1 \leq A_i \lt B_i \leq N$
$i \neq j \Rightarrow (A_i,B_i) \neq (A_j,B_j)$
入力は全て整数

解法

一般的に, 「消す」という操作よりも, 「入れる」という操作の方が簡単である場合が多い. また, この問題を解くにあたって, $k=1,2,\dots,N$ の順に解く必要がないことから, $k=N,N-1, \dots, 1$ の順に解くことにする.

$G_k:=G-\{1,2,\dots,k\}$ とする. このとき, $G_k, G_{k+1}$ の間には以下のような関係がある.

$G_{k+1}$ のグラフに, 頂点 $k$ と, $A_j=k+1$ である全ての $j$ に対して, 辺 $(k+1) B_j$ を加えると, $G_k$ になる *1.

この関係から, $G_k$ の連結成分の個数を $C_k$ としたとき, 以下のようにして, $C_N, C_{N-1}, \dots, C_1, C_0$ を求めることができる.

$C_N=0$ である ( $0$ 頂点からなるグラフの連結成分の数は $0$ である).
の順に以下を実行する.
- $C_k \gets C_{k+1}+1$ とする ( $G_{k+1}$ に孤立している頂点 $k$ を加える).
- $A_j=k+1$ である全ての $j$ に対して, 頂点 $k+1$ と頂点 $B_j$ が非連結ならば, この辺を加え, $C_k$ から $1$ を引く (非連結な頂点同士辺を結ぶと, 連結成分の数は $1$ 減る).

グラフに辺を加える, および2頂点が非連結かどうかをみることを得意とするデータ構造は Union Find である.

よって, 計算量 $O(N+M \alpha(N))$ で求めることができた.

*1: $1 \leq A_i \lt B_i \leq N$ という制約に注意