[AtCoder] ABC 157 D – Friend Suggestions

問題

方針

まず初めに、友達関係の Union-Find を作成します。このとき、人 \( i \) の友達の数を \( f_i \) として数えます。次に、人 \( i \) のブロック人数を \( b_i \) と、人 \( i \) と 人 \( j \) がブロック関係かつ 人 \( i \) と 人 \( j \) が同じグラフに所属してるとき、人 \( i \) のブロックの人数を \( b_i \) として加算します。また、\( b_j \) も加算します。人 \( i \) の連結成分の数を \( a_i \) とすると、人 \( i \) の友達候補は、\( a_i – f_i – b_i – 1 \) となります。

コード