398. How Many Pairs Can Reach Each Other
Count the pairs of distinct vertices (u, v) for which some route joins them,
counting (u, v) and (v, u) as one pair. Print that count.
Checking every pair is O(n²) and far too slow. The way through is to notice
that connectivity groups vertices completely: any two vertices in the same
component are joined, and no vertex in one component is joined to a vertex in
another.
So a component of size s contributes s × (s - 1) / 2 pairs, and the answer
is that summed over the components. Nothing is ever compared against anything
else.
At the largest size this reaches roughly five billion, so a 32-bit accumulator silently wraps to a negative number. Use a 64-bit type.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - There are no self-loops and no repeated edges.
Input
The first line contains two integers n and m, the number of vertices and
edges. Each of the next m lines contains two integers u and v, an
undirected edge between those vertices. Vertices are numbered 1 to n.
Output
Print one integer, the number of connected pairs.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.