An archipelago has n islands numbered 0 .. n-1. The list ferries holds pairs [a, b]: a ferry sails both ways between islands a and b. A traveller may change ferries on any island.
Return the number of unordered pairs of distinct islands {u, v} such that no sequence of ferries takes a traveller from u to v.
Examples
Input: n = 5, ferries = [[0, 1], [2, 3], [3, 4]]
Output: 6
Explanation: the groups are {0, 1} and {2, 3, 4}; every island of one group is cut off from each of the other: 2 * 3 = 6.
Input: n = 3, ferries = [[0, 1], [1, 2]]
Output: 0
Input: n = 4, ferries = []
Output: 6
Constraints
1 <= n <= 10**4,0 <= len(ferries) <= 2 * 10**4,0 <= a, b < n; ferries may repeat or start and end at the same island- Target: O((n + F) * alpha(n)) time.
Goals
- Compute component sizes with union by size
- Turn component sizes into a pair count without a quadratic loop