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 != biThe 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).
C++
Java
Python
C#
JavaScript
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
C++
Java
Python
C#
JavaScript
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.
| 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. |
Count Unreachable Pairs of Nodes in an Undirected Graph | Leetcode - 2316 | MICROSOFT | Live Coding • codestorywithMIK • 4,561 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