Count Unreachable Pairs of Nodes in an Undirected Graph - Solution & Explanation

Q: Is Count Unreachable Pairs of Nodes in an Undirected Graph easy or hard?

The problem is rated Medium because the main challenge is recognizing that the task reduces to counting connected component sizes. Once that insight is clear, applying DFS, BFS, or Union-Find leads to a straightforward linear-time solution.

Q: Count Unreachable Pairs of Nodes in an Undirected Graph Python/Java solution

Python and Java implementations typically build an adjacency list and run DFS or BFS to determine component sizes. Another option uses a Union-Find class to merge nodes while processing edges. Both implementations compute unreachable pairs using component size multiplication and run in O(n + m) time.

Q: How to solve Count Unreachable Pairs of Nodes in an Undirected Graph in O(n)?

First compute connected component sizes using DFS, BFS, or Union-Find in O(n + m). If component sizes are s1, s2, s3, iterate through them and accumulate pairs using size * remaining_nodes. This avoids checking every pair explicitly and reduces the computation to linear time relative to the graph size.

Q: What is the best approach for Count Unreachable Pairs of Nodes in an Undirected Graph?

The optimal solution identifies connected components and counts pairs across components. This can be implemented using Union-Find or DFS/BFS traversal. Both approaches run in O(n + m) time where n is the number of nodes and m is the number of edges. After computing component sizes, multiply each component size by the number of nodes remaining outside it to count unreachable pairs efficiently.

Q: Is Count Unreachable Pairs of Nodes in an Undirected Graph asked at Google/Amazon/Meta?

Graph connectivity and component-counting problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations involving Union-Find, connected components, or counting cross-component pairs are common in medium-level graph interview rounds.

Q: What data structure is used in Count Unreachable Pairs of Nodes in an Undirected Graph?

The problem primarily uses graph data structures such as adjacency lists along with traversal algorithms like DFS or BFS. Another common structure is the Disjoint Set Union (Union-Find) data structure, which efficiently groups nodes into connected components.

Q: What is the time complexity of Count Unreachable Pairs of Nodes in an Undirected Graph?

The optimal complexity is O(n + m), where n is the number of nodes and m is the number of edges. DFS or BFS visits each node and edge once. Union-Find also achieves near-linear complexity with path compression and union by rank, resulting in O(n + m * α(n)) which is effectively linear for practical input sizes.

MediumDepth-First Search Breadth-First Search Union Find Graph27 min readAsked at: Amazon, Microsoft, Google +1

Practice this problem

Problem Statement

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [a_i, b_i] denotes that there exists an undirected edge connecting nodes a_i and b_i.

Return the number of pairs of different nodes that are unreachable from each other.

Example 1:

Input: n = 3, edges = [[0,1],[0,2],[1,2]]
Output: 0
Explanation: There are no pairs of nodes that are unreachable from each other. Therefore, we return 0.

Example 2:

Input: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
Output: 14
Explanation: There are 14 pairs of nodes that are unreachable from each other:
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]].
Therefore, we return 14.

Constraints:

1 <= n <= 10⁵
0 <= edges.length <= 2 * 10⁵
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
There are no repeated edges.

Approach Overview

Problem Overview: You are given n nodes and an edge list describing an undirected graph. Two nodes are considered unreachable if no path exists between them. The task is to count how many pairs of nodes belong to different connected components.

The key observation: nodes inside the same connected component can reach each other, so only nodes from different components contribute to the answer. Once you know the size of each component, you can count cross-component pairs efficiently.

Approach 1: Union-Find to Identify Components (Time: O(n + m * α(n)), Space: O(n))

This method uses the Disjoint Set Union structure to group nodes into connected components while processing edges. For every edge (u, v), perform a union operation so both nodes share the same root. After processing all edges, iterate through nodes and count how many belong to each root component. If component sizes are s1, s2, s3..., the number of unreachable pairs can be computed incrementally by multiplying each size with the remaining nodes not yet processed. Union-Find with path compression and union by rank keeps operations almost constant time. This approach works well when edges arrive dynamically or when you already use Union Find in your workflow.

Approach 2: Depth-First Search to Explore Components (Time: O(n + m), Space: O(n))

Build an adjacency list for the graph, then iterate through all nodes. If a node has not been visited, run a DFS to explore its entire connected component and count its size. Each DFS traversal returns the number of nodes reachable from that start node. Similar to the union-find solution, use component sizes to accumulate unreachable pairs by multiplying the current component size with the number of remaining nodes. DFS naturally fits graph traversal problems and is easy to implement using recursion or a stack. This approach relies on standard Depth-First Search traversal on an undirected graph.

BFS works identically if you prefer a queue-based traversal using Breadth-First Search. Both DFS and BFS discover connected components in linear time.

Recommended for interviews: Both DFS and Union-Find achieve optimal O(n + m)-style performance. DFS is often quicker to implement during interviews because it only requires an adjacency list and a visited array. Union-Find demonstrates stronger knowledge of disjoint-set data structures and is useful when the problem involves repeated connectivity queries. Showing either approach signals solid graph fundamentals.

Approach 1: Union-Find to Identify Components

The Union-Find data structure can be used to efficiently determine connected components in the graph. By iterating over the edges and performing union operations, we can group nodes into their respective connected components. Once all edges are processed, nodes within the same connected component can reach each other, whereas nodes in different components cannot.

To count the number of unreachable pairs of nodes, compute the size of each component. If the total number of nodes is n, and the size of each component is c_i, the unreachable pairs are given by the sum of c_i * (n - c_i) for all components i.

This C solution builds a Union-Find structure to determine connected components. A parent array is used to track the root of each node, and a rank array helps in optimizing union operations. After processing all edges, the solution calculates the size of each component and then iteratively computes the number of unreachable pairs using the formula c_i * (n - c_i).

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n + e), where e is the number of edges, due to the union and find operations being amortized nearly constant.
Space Complexity: O(n), for storing parent, rank, and component sizes.

Try this approach in the editor →

Approach 2: Depth-First Search to Explore Components

Depth-first search (DFS) can also be employed to explore nodes and determine connected components. By traversing all nodes and initiating DFS for unvisited nodes, the graph's nodes can be segregated into connected sections. Each DFS run marks all connected nodes, constructing a component. Once the components are identified, calculating the number of unreachable pairs becomes straightforward.

The total number of pairs of nodes is (n * (n - 1)) / 2. Subtract the number of pairs within each component from this total to get the number of unreachable pairs.

This C approach constructs an adjacency list for the graph and uses DFS to explore all nodes in each component and count their sizes. Unvisited nodes initiate new DFS runs to mark nodes as part of a connected component. The number of unreachable pairs is calculated accordingly

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n + e), where e is the number of edges, using DFS to discover components.
Space Complexity: O(n + e), due to adjacency list and visit tracking.

Try this approach in the editor →

Approach 3: DFS

For any two nodes in an undirected graph, if there is a path between them, then they are mutually reachable.

Therefore, we can use depth-first search to find the number of nodes t in each connected component, and then multiply the current number of nodes t in the connected component by the number of nodes s in all previous connected components to obtain the number of unreachable node pairs in the current connected component, which is s times t. Then, we add t to s and continue to search for the next connected component until all connected components have been searched, and we can obtain the final answer.

The time complexity is O(n + m), and the space complexity is O(n + m). Here, n and m are the number of nodes and edges, respectively.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Union-Find to Identify Components	Time Complexity: O(n + e), where e is the number of edges, due to the union and find operations being amortized nearly constant. Space Complexity: O(n), for storing parent, rank, and component sizes.
Depth-First Search to Explore Components	Time Complexity: O(n + e), where e is the number of edges, using DFS to discover components. Space Complexity: O(n + e), due to adjacency list and visit tracking.
DFS	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Union-Find (Disjoint Set)	O(n + m * α(n))	O(n)	Best when connectivity needs to be tracked dynamically or edges are processed incrementally
Depth-First Search (Component Counting)	O(n + m)	O(n)	Straightforward graph traversal when the full adjacency list is available
Breadth-First Search (Component Counting)	O(n + m)	O(n)	Preferred when iterative traversal with a queue is easier than recursion

Video Solution

Count Unreachable Pairs of Nodes in an Undirected Graph | Leetcode - 2316 | MICROSOFT | Live Coding • codestorywithMIK • 8,556 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Unreachable Pairs of Nodes in an Undirected Graph easy or hard?

The problem is rated Medium because the main challenge is recognizing that the task reduces to counting connected component sizes. Once that insight is clear, applying DFS, BFS, or Union-Find leads to a straightforward linear-time solution.

Count Unreachable Pairs of Nodes in an Undirected Graph Python/Java solution

Python and Java implementations typically build an adjacency list and run DFS or BFS to determine component sizes. Another option uses a Union-Find class to merge nodes while processing edges. Both implementations compute unreachable pairs using component size multiplication and run in O(n + m) time.

How to solve Count Unreachable Pairs of Nodes in an Undirected Graph in O(n)?

First compute connected component sizes using DFS, BFS, or Union-Find in O(n + m). If component sizes are s1, s2, s3, iterate through them and accumulate pairs using size * remaining_nodes. This avoids checking every pair explicitly and reduces the computation to linear time relative to the graph size.

What is the best approach for Count Unreachable Pairs of Nodes in an Undirected Graph?

The optimal solution identifies connected components and counts pairs across components. This can be implemented using Union-Find or DFS/BFS traversal. Both approaches run in O(n + m) time where n is the number of nodes and m is the number of edges. After computing component sizes, multiply each component size by the number of nodes remaining outside it to count unreachable pairs efficiently.

Is Count Unreachable Pairs of Nodes in an Undirected Graph asked at Google/Amazon/Meta?

Graph connectivity and component-counting problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations involving Union-Find, connected components, or counting cross-component pairs are common in medium-level graph interview rounds.

What data structure is used in Count Unreachable Pairs of Nodes in an Undirected Graph?

The problem primarily uses graph data structures such as adjacency lists along with traversal algorithms like DFS or BFS. Another common structure is the Disjoint Set Union (Union-Find) data structure, which efficiently groups nodes into connected components.

What is the time complexity of Count Unreachable Pairs of Nodes in an Undirected Graph?

The optimal complexity is O(n + m), where n is the number of nodes and m is the number of edges. DFS or BFS visits each node and edge once. Union-Find also achieves near-linear complexity with path compression and union by rank, resulting in O(n + m * α(n)) which is effectively linear for practical input sizes.

Ready to solve this problem?

Practice Count Unreachable Pairs of Nodes in an Undirected Graph with our built-in code editor and test cases.

Practice on FleetCode

Number of Islands

Problem Info

DifficultyMedium

Acceptance49.9%

Approaches3

Reading time27 min

Asked at

Amazon Microsoft Google Snapchat

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Union-Find to Identify Components

Code

Complexity

Approach 2: Depth-First Search to Explore Components

Code

Complexity

Approach 3: DFS

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents