789. Unreachable Pairs
A mountain region has n villages numbered 0 to n - 1. Each entry [a, b] in edges is a footpath that can be walked in both directions between villages a and b.
Two different villages are cut off from each other if no chain of footpaths leads from one to the other. Count the unordered pairs of different villages that are cut off from each other (the pair {x, y} is the same as {y, x}) and return that count. The count can exceed the 32-bit range, so it is returned as a 64-bit integer. Duplicate footpaths and footpaths from a village to itself may appear.
Example 1
- Input:
- n = 6, edges = [[5,0],[0,2],[3,4]]
- Output:
- 11
- Explanation:
The clusters are {0,2,5}, {3,4} and {1}, of sizes 3, 2 and 1, so the cut-off pairs number 3*2 + 3*1 + 2*1 = 11.
Example 2
- Input:
- n = 5, edges = [[4,4],[1,3],[3,1]]
- Output:
- 9
- Explanation:
Only villages 1 and 3 are linked (the loop at 4 changes nothing), so 10 - 1 = 9 of the 10 pairs are cut off.
Example 3
- Input:
- n = 3, edges = [[2,0],[0,1]]
- Output:
- 0
- Explanation:
All three villages are connected through village 0, so no pair is cut off.
Constraints
- 1 ≤ n ≤ 105
- 0 ≤ edges.length ≤ 2 * 105
- 0 ≤ a, b < n for every
[a, b]
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 300 msC++ 75 msJava 150 msJavaScript 150 msTypeScript 150 ms
Expected complexity
- Time
- O((n + m) * alpha(n))
- Space
- O(n)