ABC260 F - Find 4-cycle (500)
愚直に全パターンを試すと$ \mathcal{O}(S^2T^2)かかる
ある2つの間の共通の頂点を探すには$ \mathcal{O}(S^2T)か$ \mathcal{O}(ST^2)かかる
解説の解法
それぞれのSについて辺で結ばれている$ Tのペアを探索
あるペアについてまだそのペアが発見されていないならば発見した扱いにする
これ用に長さTの2次元配列を持っておく
発見していた場合、そのときのSと今のSを使えばサイクルになるのでそれを出力すれば良い
一見$ \mathcal{O}(ST^2)だが鳩ノ巣原理より$ T^2+1回目のペアでは既存の$ T^2個のいずれかと同じペアになるので$ O(T^2)