1026. Groups Where Everyone Knows Everyone

A club has n members and m acquaintances, each between two different members. No pair is listed twice. Acquaintance is passed along for the purpose of grouping: two members are in the same GROUP when a chain of acquaintances joins them.

A group is COMPLETE when every pair of its members is directly acquainted, not merely joined through others. Print how many groups are complete.

6 members, pairs (1 2)(2 3)(1 3)(4 5) -> 3

The triangle 1, 2, 3 is complete, the pair 4, 5 is complete, and member 6 is a group of one which is complete because it has no pair to check. That is three.

4 members, pairs (1 2)(2 3) -> 1 5 members, pairs (1 2)(1 3)(1 4)(2 3)(2 4) -> 1

The first of those has a chain of three missing the pair between its ends, and a lone fourth member, so only that member counts. The second has four members short of one of their six pairs, and again only the lone fifth member counts.

## What most people try first

Build the groups, then check every pair inside each one against a set of the listed pairs. A group of s members has s(s-1)/2 pairs, so on one big group that is 5 * 10^9 lookups.

## Count the members and the acquaintances of each group

A group of s members is complete exactly when it holds s(s-1)/2 acquaintances, because that is how many pairs it has and no pair is listed twice.

merge along every pair, keeping the member count on each root walk the pairs again, adding 1 to a counter on the root of each for each root r: s = members[r], e = acquaintances[r] complete if 2 * e == s * (s - 1)

Two passes over the pairs, and no pair is ever tested against another.

## Why the count decides it

Every listed acquaintance has both ends in one group, so tallying by root splits the m pairs across the groups with none left over and none counted twice. A group of s members has at most s(s-1)/2 distinct pairs, and since no pair is listed twice, holding that many means holding all of them.

The condition would be wrong if a pair could be listed twice, which is why the input forbids it. It would also be wrong with a member acquainted with itself, which the input forbids for the same reason.

## Comparing without dividing

Write the test as 2 * e == s * (s - 1) rather than e == s * (s - 1) / 2. The product s(s-1) is always even so the division is exact either way, but the multiplied form has no division at all and is the one that reads the same in every language.

## Overflow

For a group of s members the product s(s-1) passes 2^32 once s reaches 65536, and at s = 10^5 it is about 10^10, well past the 2147483647 a signed 32 bit integer holds. Compute it in 64 bits.

No test in this set is large enough to make a 32 bit build print a wrong answer, and the reason is worth knowing: a group that large needs at least s - 1 acquaintances to be connected at all, and m stops at 2 * 10^5, so only groups with s at most 632 can ever be complete here. It is still the wrong arithmetic, and on a version of this problem with a larger m it would give a wrong answer rather than a slow one.

## The group of one

A single member has no pair, so s(s-1)/2 is 0, it holds 0 acquaintances and it is complete. Every isolated member counts, which is what makes the first example answer 3 rather than 2.

## Cross-reference

Problem 383 asks whether the WHOLE graph is complete, which is one comparison of m against n(n-1)/2 and needs no grouping at all. Splitting the same test across the groups is what this problem adds.

## Cost

Time O((n + m) alpha(n)). Space O(n).

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` and `u` is never equal to `v`. - No pair is listed twice, in either order.