Official

F - Find 4-cycle Editorial by Nyaan

この問題はいくらかのひらめき要素を要求しているので、途中で解法に気づいた読者の方のためにヒント形式で解説を書きます。

ヒント1 $V_2$ に含まれる頂点対 $(x,y)$ は全部で $\mathrm{O}(T^2)$ 通りです。$T^2 \simeq 10^7$ で、これは十分小さいです。

ヒント2 $V_2$ に含まれるある頂点対 $(x,y)$ に対して、$x,y$ の両方に隣接する $V_1$ 内の頂点が 2 個見つかったとします。(それぞれ $z, w$ とする。) このとき、$(x, y, z, w)$ は 4-cycle をなします。この「2 個見つかったらよい」という部分がポイントです。

ヒント3 ヒント1,2 に加えてある数学的な発想を用いることで、高速なアルゴリズムを構成することができます。

ヒント4 その発想とは「鳩ノ巣原理」と呼ばれるものです。

解法 以下の手続きで説明されるアルゴリズムを用いればこの問題を解くことができます。

  • 添え字が $V_1$ の頂点、リスト内の要素が $V_2$ の頂点となるような隣接リスト $L$ に $G$ の辺を保存する。
  • 添え字に $V_2$ の頂点を取る $T \times T$ の二次元配列 $M$ を用意する。はじめ、$M$ の要素はすべて $-1$ で初期化されている。
  • $z \in V_1$ について $L[z]$ ($z$ に隣接する頂点が保存されたリスト) を for x in L[z]: for y in L[z]:という風な二重 for 文で走査する。
  • for 文内での処理は以下のように行う。
    • $x=y$ の場合、何もせずに continue する。
    • $x \neq y$ の場合、$M[x][y]$ の値を参照して場合分けを行う。
      • $M[x][y]$ の値が $-1$ の場合、$x,y$ の両方に隣接する頂点はこれ以前に発見されていないことを意味する。よって、$M[x][y] = z$ として continue する。
      • $M[x][y]$ の値が $-1$ でない場合、$w = M[x][y]$ とする。$w$ は $x,y$ の両方に隣接する頂点である。よって $x,y,z,w$ は 4-cycle をなすので、これを出力してプログラムを終了する。
  • すべての $z$ を走査して 4-cycle を発見できなかった場合は -1 を出力してプログラムを終了する。
正当性は、どのようなサイクルでも上記のアルゴリズムによって検出できることを確認することで示せます。
計算量を考えます。このアルゴリズムの計算量はアルゴリズムの最も内側のループで探索する頂点の組 $(z, x, y)$ としてあり得るものの個数に依存します。 $x=y$ と $x \neq y$ で場合分けして考えましょう。
$x=y$ の場合は $z-x$ 間に辺がある頂点対 $(z, x)$ の個数が上界になり、辺の本数 $M$ で抑えられます。
$x \neq y$ の場合は鳩ノ巣原理を用いると $T(T-1)+1$ が上界であることを示せます。配列 $M$ の $x\neq y$ でない要素の個数は $T(T-1)$ 個あるのと、同じ要素に 2 回アクセスするとプログラムを終了するというアルゴリズムの性質から、$(z,x,y)$ を $T(T-1)+1$ 回走査した時点で $2$ 回以上アクセスする要素が 1 個以上存在してプログラムが終了することが確認できます。
以上より、この問題を $\mathrm{O}(S+M+T^2)$ で解くことができました。

posted:
last update: