Kazun の競プロ記録

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

AtCoder Beginner Contest 293 D問題 Tying Rope

AtCoder ABC293 ABC 400 pts D問題

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

問題

提出解答

問題の概要

$N$ 本のロープがある. 各ロープにはそれぞれ $1$ 以上 $N$ 以下の番号が振られている. また, 各ロープの一方の端は赤で塗られており, 他方の端は青で塗られている.

以下の操作を $M$ 回行う.

ロープ $A_j$ の色 $B_j$ とロープ $C_j$ の色 $D_j$ を結ぶ. なお, 色 $\texttt{R}$ とは赤色を, 色 $\texttt{B}$ とは青色を表す.

なお, $M$ 回の操作において, 各ロープにおいて, 同じ端が $2$ 回以上登場しない.

このとき, ひとつながりになっているロープの組について環状になっているものの個数 $X$ とそうでないものの個数 $Y$ をそれぞれ求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq M \leq 2 \times 10^5$
$1 \leq A_j, C_j \leq N$
$B_j, D_j$ は $\texttt{R}, \texttt{B}$ のどちらか一方
$(A_j, B_j). (C_j, D_j)~(j=1,2, \dots, M)$ は全て異なる.

解法

ロープの端を頂点, 結ばれている関係を辺とするグラフを構成する.

具体的には以下のようにして無向グラフ $G=(V,E)$ を構成する.

$V:=\{(i, \texttt{R}) \mid i=1,2, \dots, N\} \cup \{(i, \texttt{B}) \mid i=1,2, \dots, N\}$
$E:=\{(i, \texttt{R})(i, \texttt{B}) \mid i=1,2, \dots, N\} \cup \{(A_j,B_j)(C_j, D_j) \mid j=1,2, \dots, N\}$

なお, $E$ の集合の和集合について, 左側は元から同じロープであること, 右側は操作によってつながった部分を表す.

ここで, 各頂点は制約から次数が $1$ または $2$ である. よって, 各連結成分はパスかサイクルになる.

この条件下では $n$ 頂点の連結成分において, パスは辺の数が $(n-1)$ で, サイクルは $n$ になる.

よって, 辺数が超点数未満の連結成分の数が $X$ , 頂点数と辺数が等しい連結成分の数が $Y$ である.

これを求めるためには BFS, DFS や Union Find を利用することにより, $O(N+M), O(N+M \alpha (N))$ 時間で求めることができる.