D - New Friends Editorial by en_translator
Consider a graph whose vertices represent the users and edges the friendship relationships.
Since the operation always add an edge between vertices belonging to the same connected component, the number of connected components always stays invariant.
Conversely, any vertices belonging to the same connected component can be directly connected by an edge after a repetition of the operations.
Proof
Take two vertices $X$ and $Y$ that belong to the same connected component. Take an arbitrary simple path from $X$ and $Y$, denoting the vertices by $X=v_0,v_1,v_2,\ldots,v_m=Y$. We can add an edge between $v_0$ and $v_i$ (if it does not exist) for each $i=2,3,\ldots$ in order.Since a connected component with \(n\) vertices has at most \(\frac{n(n-1)}{2}\) edges, the sought answer is the sum of this value over the connected components minus the number of original edges.
Therefore, this problem can be solved by finding the number of edges in each connected component using BFS (Breadth-First Search), DFS (Depth-First Search) or DSU (Disjoint Set Union). The complexity is \(O(N+M)\).
posted:
last update: