geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Biginner Contest 260 F - Find 4-cycle

グラフ ABC コンテスト後鳩の巣原理

コンテスト後に自力ACしましたが、記事を書いていて計算量の見積もりが誤っていたので、公式解説を読みました。

頂点集合 $U,V$ を以下の通りとします。

$U = \{1,\ 2,\ \cdots ,\ S\}$
$V = \{S+1,\ S+2,\ \cdots ,\ S+T\}$

$U,V$ は独立集合であるという条件から、4-cycleをもつ条件は以下に限定されます。

$U$ に属するある頂点 $u_i,u_j$ と、 $V$ に属するある頂点 $v_k,v_l$ であって、 $u_i,u_j$ のいずれも $v_k,v_l$ の両方に辺がある

そこで、

$U$ に属する頂点 $u_i$ が、頂点 $V$ に属する2つの頂点 $v_j, v_k$ の両方と辺を持つ

という場合に、それを

$u_i$ が頂点対 $(v_i, v_j)$ を持つ

という風に表現したとき、4-cycleを探すという問題は、

$U$ から共通の頂点対を持つ2つを見つける

という問題に言い換えられます。

そこで、以下のような解法が考えられます。

$i=1,\ 2,\ \cdots ,\ S$ について、以下を行う。

$u_i$ と繋がる頂点を $v_1,\ v_2,\ \cdots ,\ v_{m_i}$ とする。
ここから得られる全ての頂点対 $(v_j,v_k)$ について、 $u_i$ が持っているということを記録していく。ここで、既に別の $u_x$ が、頂点対 $(v_j,v_k)$ を持っていた場合、 $(u_x,u_i,v_j,v_k)$ を答えとして出力する。

これでACしましたが、問題を解いた後に上記の部分の計算量の見積もりが誤りだったと気づきました。公式解説を見たところ、鳩の巣原理により $O(T^2)$ となることがわかりました。

これは、 $(v_i,v_j)$ という組は高々 $T^2$ 個しかないので、頂点対を調べていくと、高々 $T^2 + 1$ 回で既に一度調べた頂点対が現れる、ということです。

細かい実装の話に移りますが、C++で頂点対をpairとして、mapに記録する方法だとTLEしました。
二次元配列に記録していく方法だと、ACできました。配列として持てる場合は、mapは使用しない方が良さそうです。

Submission #33385373 - AtCoder Beginner Contest 260