Count Pairs of Nodes That Cannot Reach Each Other
Problem statement
An undirected graph has n nodes numbered 0 to n - 1 and the given edges. Two nodes can reach each other when a path of edges connects them.
Return how many pairs of different nodes {u, v} (each pair counted once) cannot reach each other. The answer can be larger than a 32-bit integer.
Function
countUnreachablePairs(n: int, edges: int[][]) → longExamples
Example 1
n = 5edges = [[0,1],[3,4]]return = 8The groups of connected nodes are {0, 1}, {2} and {3, 4}. Of the 10 pairs of nodes, only (0, 1) and (3, 4) can reach each other, so 8 pairs cannot.
Example 2
n = 4edges = [[0,1],[1,2],[2,3]]return = 0The edges form one path through all four nodes, so every pair can reach each other: 0.
Example 3
n = 1edges = []return = 0One node has no pairs at all.
Constraints
1 <= n <= 10^50 <= edges.length <= 5000- each
edges[i] = [a, b]with0 <= a, b < nanda != b; no edge is listed twice