Count Unreachable Pairs
MediumUnion Find · Adobe
You are given an integer n and an undirected graph with nodes labeled 0 to n - 1. edges[i] = [a, b] means there is an edge between nodes a and b.
Return the number of unordered pairs of different nodes {u, v} such that there is no path between u and v. Count each pair once.
Example 1
- Input:
- n = 6, edges = [[0,3],[3,5],[1,4]]
- Output:
- 11
- Explanation
- The components are {0,3,5}, {1,4} and {2}. Every pair from two different components is unreachable: 3×2 + 3×1 + 2×1 = 11.
Example 2
- Input:
- n = 4, edges = [[0,1],[1,2],[2,3]]
- Output:
- 0
- Explanation
- The edges link all four nodes into one chain, so every node can reach every other.
Example 3
- Input:
- n = 3, edges = []
- Output:
- 3
- Explanation
- There are no edges, so all 3 possible pairs are unreachable.
Constraints
1 <= n <= 10^50 <= edges.length <= 2 * 10^5edges[i] = [a, b]with0 <= a, b < nanda != b- There are no repeated edges