ユーザを頂点、友達関係を辺としたグラフを考えます。

操作は、すでに同じ連結成分に属する頂点の間に辺を追加するものであるため、連結成分が変化することはありません。

逆に同じ連結成分に属する頂点同士は、操作の繰り返しにより必ず直接辺で結ぶことができます。

頂点数 \(n\) の連結成分には最大で \(\frac{n(n-1)}{2}\) 本の辺が存在できるため、求める答えは、この値の連結成分ごとの和からもともと存在する辺の個数を引いたものです。

よって、BFS/DFSやUnion-Findなどにより各連結成分の頂点数を求めることでこの問題を解くことができます。計算量は \(O(N+M)\) です。