Kazun の競プロ記録

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

AtCoder Beginner Contest 251 F問題 Two Spanning Trees

AtCoder ABC ABC251 F問題 500 pts

問題

提出解答

問題の概要

連結単純無向グラフ $G=(V=[\![N]\!], E=\{u_j v_j \mid j=1,2, \dots, M\})$ がある.

次を満たす $G$ の全域部分グラフ $T=(V,F), U=(V,H)$ を一つずつ求めよ.

$T$ を頂点 $1$ を根付き木としたとき, 任意の $e \in E \setminus F$ に対して, $e=xy$ とすると, $x,y$ は $T$ において先祖と子孫の関係である.
$U$ を頂点 $1$ を根付き木としたとき, 任意の $e \in E \setminus H$ に対して, $e=zw$ とすると, $z,w$ は $U$ において先祖と子孫の関係ではない.

制約

$1 \leq N \leq 2 \times 10^5$
$N-1 \leq M \leq \min \left(2 \times 10^5, \frac{N(N-1)}{2} \right)$
$1 \leq u_j, v_j \leq N$
$G$ は連結単純無向グラフ.

解法

結論からいうと, $T$ として頂点 $1$ から開始する $G$ の DFS 木, $U$ として頂点 $1$ から開始する $G$ の BFS 木とすればよい.

証明は公式の解説を参考にすること.

よって, $G$ に対する DFS と BFS をすればよく. これらはともに計算量 $O(N+M)$ で求めることができる.