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.

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.

Description Hints 3 Solution Video 28:24

2316. Count Unreachable Pairs of Nodes in an Undirected Graph

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: 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.

Medium49.9% acceptance4 companies

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.

Asked at 4 companies

Snapchat Amazon

Google Microsoft

Topics

Hints open one at a time

Hint 1

Find the connected components of the graph. To find connected components, you can use Union Find (Disjoint Sets), BFS, or DFS.

Hint 2

For a node u, the number of nodes that are unreachable from u is the number of nodes that are not in the same connected component as u.

Hint 3

The number of unreachable nodes from node u will be the same for the number of nodes that are unreachable from node v if nodes u and v belong to the same connected component.

28:24

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution