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] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.
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 <= 1050 <= edges.length <= 2 * 105edges[i].length == 20 <= ai, bi < nai != biProblem 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.
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).
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 (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
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.
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.
| 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. |
| Depth-First Search to Explore Components | Time Complexity: O(n + e), where e is the number of edges, using DFS to discover components. |
| DFS | — |
| 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 |
Count Unreachable Pairs of Nodes in an Undirected Graph | DSU | Leetcode 2316 | Graph Concepts- 23 • codestorywithMIK • 16,743 views views
Watch 9 more video solutions →Practice Count Unreachable Pairs of Nodes in an Undirected Graph with our built-in code editor and test cases.
Practice on FleetCode