FastPrepCount Pairs of Nodes That Cannot Reach Each Other
Problems/Count Pairs of Nodes That Cannot Reach Each Other

Count Pairs of Nodes That Cannot Reach Each Other

Adobe logoAdobe● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: This problem counts how many pairs of nodes in a graph with two-way edges have no path between them, an answer that can pass the 32-bit range. An Adobe MTS-2 (Java) report gives this as the second of two questions in its first DSA round, only as a link to the well-known problem on unreachable node pairs, and notes that this elimination round wanted working code with the best possible time and memory; it gives no examples or limits of its own.

Our choices: the usual rules of that problem (pairs counted once, no self-loops or repeated edges), up to 10^5 nodes but at most 5000 edges, a 64-bit result, and new examples.

The judged task matches the report at about 90%.

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[][]) → long

Examples

Example 1

n = 5edges = [[0,1],[3,4]]return = 8

The 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 = 0

The edges form one path through all four nodes, so every pair can reach each other: 0.

Example 3

n = 1edges = []return = 0

One node has no pairs at all.

Constraints

  • 1 <= n <= 10^5
  • 0 <= edges.length <= 5000
  • each edges[i] = [a, b] with 0 <= a, b < n and a != b; no edge is listed twice

More Adobe problems

  • Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
  • All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
  • Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
All Adobe interview questionsSee Adobe hiring insights
Saved
public long countUnreachablePairs(int n, int[][] edges) {
    // Write your code here.
}
Checking account…