ABC016 C - 友達の友達
解法
幅優先っぽいことをしようと思いますが、2つ先のみを見ればいいので、そのようにします。
制限もとても小さいので、割と何をしても大丈夫です。
まずは、入力をしていきます。
memo[i][j] = iとjが友達かどうか、としていき、友達なら1、そうでなければ0とでもしておきましょう。
今、ユーザーxについての、友達の友達の人数を調べることにします。
まずは、友達をすべて列挙します。
先ほどのメモをみて、友達だったらvectorに挿入、とでもしておけば十分です。
あとは、そのvectorの要素すべてに対して、n人と友達であるかどうかを調べれば完了です。
そのとき、そもそもxと友達であった場合や、被っているパターンを排除できるようにしましょう。
サイズがnの配列を用意して、xの友達の友達であれば1、そうでなければ0として記録していき、最終的にその要素を確認して和をとっていく、という方法をとると重複せずに数えることができます。
あとは、これを全てのxに対して行っていけばいいです。
