D1 - Dual Friendship [Easy]

概要

この問題のコンセプトは「読解」と「計算量の見積もり」です．

問題の意味をしっかりと整理し，方針を立てましょう．

愚直に実装すると TLE(実行時間制限超過) となる場合がありましが，少しの工夫で無駄が省けます．

問題原案：@machoniump, @uni_kakurenbo

解説

$Ⅰ.$ 考察のポイント

パッと見では条件が分かりづらいかもしれませんが，題中で使われている要素を丁寧に分解していくことで問題の全体像が見えてきます．
互いに友達や友達の友達の表す内容をよく確認しておきましょう．

$Ⅱ.$ 愚直解と計算量の削減

$\mathrm{D_1}\>\text{[Easy]}$

制約より $N$ は $3000$ 以下ですから，「人 $p$ と人 $q$ とが友達の友達である」かどうかを高速に判定することができれば，$(p, q)$ の組を全探索することで解を求められそうです．

では，$1 \leq s, t \leq N$ として「人 $s$ と人 $t$ とが友達の友達である」ことはどのように判定すればよいでしょうか．
案の一つとして「$1 \leq v \leq N$ を満たす $v$ を全探索する」ということが挙げられます．
組 $(s, t)$ ごとに，その双方と互いに友達である $v$ が存在するかを判定すればよいです．
しかし，このときの判定にかかる時間計算量は $O(N)$ ですから，全体で $O(N^3)$ となってしまうため今回の制約下では間に合いません．

ではどうしたらよいのでしょうか．
この判定方法の無駄に気づくことが重要です．

$2$ 人 $s, t$ との双方と互いに友達である人が存在するかを判定したいので，人 $s$ または 人 $t$ のうちいずれかと互いに友達である人だけを見ればよいでしょう．
たとえば人 $s$ について考えるとすると，人 $s$ と互いに友達であるすべての人について「人 $t$ と互いに友達である」かどうかを判定するだけでよいです．

では，このときの計算量はどうでしょうか．
一見先ほどと大して変わらないようにも見えますが，実際にはもっと少なく見積もってよいです．
というのも，一つの $s$ を探索するごとに参照される $v$ の個数(=友好関係の個数)を合計しても高々 $2M$ 個にしかならないからです．
たとえば $u, v$ の $2$ 人を結ぶ友好関係があったとすると，その友好関係が参照されるのは $s = u$ のときか $s = v$ のときの $2$ 通りのみになります．

したがって，この探索方法を用いたときの時間計算量は全体で $O(NM)$ になります．

ただし，

• ある人と互いに友達である人を列挙する
• ある $2$ 人が互いに友達であるかを判定する

ことが高速にできるデータ構造を用いる必要があります．

$\scriptsize \mathrm{D_2}\>\text{[Hard]}$

問題 D2 の制約は $N, M \leq 2 \times 10^5$ であるため，D1 と同じように組 $(p,q)$ を全探索していたのでは間に合いません．
ではどうするか．少し視点を変える必要があります．

全探索の対象が $2$ つあるため，このままでは難しそうです．
ここで，$p, q$ の代わりに $r$ を全探索してみてはどうでしょうか．

実は，$u$ が与えられたときに「人 $s$ と人 $t$ とが人 $u$ を介して友達の友達である」ような $(s, t)$ の組が何通りあるかは $O(1)$ で求めることができます． 「$u$ と互いに友達である人」は「自分以外の『$u$ と互いに友達である人』すべて」と友達の友達になりうるからです．
つまり，$u$ と互いに友達であるような人の数を $\delta(u)$ とあらわすとすると，「人 $s$ と人 $t$ とが人 $u$ を介して友達の友達である」ような $(s, t)$ の組の個数は $\delta(u)(\delta(u) - 1)$ 個になります．
掛け算の前に $1$ を引くのは $s=t$ となる組を除外するためです．

問われている条件には $p < q$ が含まれるので，最後に $2$ で割ることで答えが求まります．
このときの時間計算量は $O(N)$ です．

---

実はもっと思考が単純な解法も存在します．
$s$ を全探索し，人 $s$ と互いに友達である全ての人において，その人と(人 $s$ 以外で)互いに友達である人が何人いるかを答えに加算していけばよいです．
この場合も最後に $2$ で割ります．
時間計算量は $O(N+M)$ です．

$Ⅲ.$ 発展

$1)$ 類題

(難易度順)
解法自体は同類ではないものも含まれます．

• ABC 225 $\hspace{0.15em}$ B - Star or Not
• ABC 061 $\hspace{0.15em}$ B - Counting Roads
• ABC 262 $\hspace{0.15em}$ B - Triangle (Easier)
• ABC 209 $\hspace{0.15em}$ D - Collision
• ABC 016 $\hspace{0.15em}$ C - 友達の友達

実装例

$\mathrm{D_1}\>\text{[Easy]}$

$\\$

$\mathrm{D_2}\>\text{[Hard]}$

別解 [C++]

別解 [Python]

余談

問題を書きあげてテストケースの準備をしていたら最近の ABC262-B で類似の問題が出題されたり「友達の友達」というタイトルの問題が既に出題されていることが発覚したりしてとても驚きました。
問題を見たときには「まさか」と思わず笑ってしまいましたが，折角なので類題に載せさせていただきました。