AtCoder Beginner Contest 260 F問題 Find 4-cycle

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

頂点数が $S+T$ , 辺の数が $M$ の二部グラフ $G=(X \coprod Y, E)$ がある. ここで,

$X:=\{1,2, \dots, S\}, Y:=\{S+1, S+2, \dots, S+T\}$
$E:=\{u_j v_j \mid j=1,2, \dots, M\}$

この $G$ おいて, 長さ $4$ のサイクル $C_4$ は存在するか? 存在するならば, $C_4$ を成す頂点の一例を求めよ.

制約

$2 \leq S \leq 3 \times 10^5$
$2 \leq T \leq 3000$
$4 \leq M \leq \min(ST, 3 \times 10^5)$
$1 \leq u_j \leq S \lt v_j \leq S+T$

解法

$G$ が二部グラフなので, $G$ に $C_4$ が存在することと, 以下は同値である.

以下を満たす $y,y' \in Y~(y \neq y')$ が存在する: $G$ における $y, y'$ の共通近傍の頂点数が $2$ 以上

実際, $y, y'$ の共通近傍で $x,x' \in X~(x \neq x')$ としたとき, $x,y,x',y'$ が $C_4$ を成す. 逆に $C_4$ が存在する場合は $Y$ 側の頂点を取ってくればよい.

$X$ 側の頂点 $x \in X$ における次数を $d_x$ としたとき, $x$ が共通近傍になるような $y,y' \in Y~(y \leq y')$ の取り方は $k_x:=\dfrac{d_x (d_x-1)}{2}$ 通りである. そのような頂点対の集合を $\mathcal{H}_x:=\{(a,b) \mid a,b: x {\text の近傍}, a \lt b \}$ と書く. このとき, $\left| \mathcal{H}_x \right|=k_x$ である.

このとき, $\displaystyle \sum_{x \in X} k_x \gt \dfrac{T(T-1)}{2}$ であるとする. このとき, $\mathcal{H}_1, \dots, \mathcal{H}_S$ から合計 $\left(\dfrac{T(T-1)}{2}+1 \right)$ 個を抜き出すと, 鳩ノ巣原理より, 異なる集合から同じ順序対 $(y,y')$ を取ることができる. この $(y,y')$ が $\mathcal{H}_x, \mathcal{H}_{x'}$ から取ってきたとすると, $x,x'$ が $y,y'$ の共通近傍であるから, $C_4$ が存在することになる.

以上から, $\displaystyle \sum_{x \in X} k_x \gt \dfrac{T(T-1)}{2}$ のときは, $x=1,2, \dots, S$ の順に $\mathcal{H}_x$ を生成すると, $\left(\dfrac{T(T-1)}{2}+1 \right)$ 個目の対を生成した時点で同じ対が発生するので, その対と発生箇所を出力すればよい.

一方で, $\displaystyle \sum_{x \in X} k_x \leq \dfrac{T(T-1)}{2}$ のときは, $\mathcal{H}_1, \dots, \mathcal{H}_S$ を全て生成し, 重複があるかどうかを見ればよい. このとき, 対の数は合計で $\displaystyle \sum_{x \in X} k_x=O(T^2)$ 個である.