ABC 157 D - Friend Suggestions

初手の方針

隣接リストを作ってdfsでカウントするような方針。グループに属する人数を求めると計算量は(n^ 2)かな？今回はnが10^ 5なので間に合わず後述するUnion-Findというデータ構造で工夫する必要がある。

Union-Findというデータ構造で実装する、グループの親を決めてグループに属する子を全て親に紐付かせるというもの。今回のようにグループの人数を求める場合隣接リストだと計算量(n)となるところUnion-Findだと(1)で済む。

ある要素の友達候補は

グループの人数 - (グループに属する友達の数+グループに属するブロックの数) - 自分自身

今回の実装で重要な概念は以下の4つ

木の連結を行う。独立した要素同士の場合はどちらか一方を親にして親1-子1の木を作り、木と木or木と独立した要素の場合はサイズが大きいものにサイズが小さいものを紐付けて新たな木を作る。

要素が属するグループの親を返す。実装ではvector<ll> par;で表現しており、uniteする際に必要があれば親を更新する。

今回はブロックという概念が存在するので対象が自身が属するグループ内に存在するかの判定に用いる。

グループの人数を返す。 map<ll, ll> s で表現しており、初期状態では全てサイズは1。実装としては要素の親のmapであるs[root(x)]を返すのでuniteで併合する際にこのマップの更新を行っている。

入力例3を例にとるとこのようになる。

f:id:iwsksky:20200316023410j:plain

概念として理解した上で手を動かさないと本番では使えないと改めて感じたのでした。