Count Unreachable Pairs of Nodes in an Undirected Graph
MedPrompt
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 != bi- There are no repeated edges.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly follows the problem definition by checking every possible pair of nodes. For each pair, it determines if they are connected by a path in the graph.
Algorithm
- Build an adjacency list representation of the graph.
- Initialize
unreachable_count = 0. - Loop for
ifrom0ton-1. - Inner loop for
jfromi+1ton-1. - Inside the inner loop, call a function
areConnected(i, j)which performs a BFS/DFS starting fromi. - If
areConnectedreturnsfalse, incrementunreachable_count. - Return
unreachable_count.
Walkthrough
The algorithm iterates through all unique pairs of nodes (i, j) where i < j. For each pair, a graph traversal like Breadth-First Search (BFS) or Depth-First Search (DFS) is initiated from node i. The traversal explores all nodes reachable from i. If node j is not visited by the end of the traversal, the pair (i, j) is considered unreachable, and a counter is incremented. This process is repeated for all n * (n - 1) / 2 pairs. First, an adjacency list representation of the graph is built from the edges array.
public long countUnreachablePairs(int n, int[][] edges) { if (edges.length == 0) { return (long)n * (n - 1) / 2; } List<Integer>[] adj = new ArrayList[n]; for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); } for (int[] edge : edges) { adj[edge[0]].add(edge[1]); adj[edge[1]].add(edge[0]); } long unreachableCount = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (!areConnected(i, j, n, adj)) { unreachableCount++; } } } return unreachableCount;} private boolean areConnected(int start, int end, int n, List<Integer>[] adj) { Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[n]; queue.offer(start); visited[start] = true; while (!queue.isEmpty()) { int node = queue.poll(); if (node == end) { return true; } for (int neighbor : adj[node]) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); } } } return false;}Complexity
Time
O(N^2 * (N + E)). There are O(N^2) pairs. For each pair, we perform a graph traversal which takes O(N + E) time in the worst case. This is computationally prohibitive for the given constraints.
Space
O(N + E). O(N + E) for the adjacency list and O(N) for the `visited` array and queue/stack used in each traversal.
Trade-offs
Pros
Simple to understand and implement directly from the problem definition.
Cons
Extremely inefficient and will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
Performs a lot of redundant work by re-calculating reachability for nodes within the same component multiple times.
A much more efficient approach is to realize that two nodes are unreachable if and only if they belong to different connected components. The problem then transforms into: find all connected components, get their sizes, and calculate the number of pairs of nodes that can be formed by picking one node from two different components.
Algorithm
- Construct an adjacency list from the
edges. - Initialize a
visitedarray of sizento allfalse. - Initialize
unreachable_pairs = 0andremaining_nodes = n. - Iterate through each node
ifrom0ton-1. - If
visited[i]isfalse:- Start a traversal (e.g., BFS) from
i. - Count the number of nodes in the component (
component_size). - Mark all nodes in the component as visited.
- Add
component_size * (remaining_nodes - component_size)tounreachable_pairs. - Subtract
component_sizefromremaining_nodes.
- Start a traversal (e.g., BFS) from
- Return
unreachable_pairs.
Walkthrough
The core idea is to count the sizes of all disjoint connected components in the graph. Let the sizes of the k components be s_1, s_2, ..., s_k. A node in a component of size s_i is unreachable from any node in any other component s_j (where j != i). We can calculate the total number of unreachable pairs with a combinatorial trick. If we have processed some components and have remaining_nodes left to visit, and we find a new component of size current_component_size, then each of the current_component_size nodes is unreachable from each of the remaining_nodes - current_component_size nodes. We add current_component_size * (remaining_nodes - current_component_size) to our total and then update remaining_nodes.
The algorithm proceeds as follows:
- Build an adjacency list for the graph.
- Create a
visitedboolean array to keep track of visited nodes. - Initialize
unreachable_pairs = 0andremaining_nodes = n. - Iterate from node
0ton-1. If a nodeihas not been visited, it means we've found a new connected component. - Start a traversal (BFS or DFS) from
ito find all nodes in this component and count its size. - Update the
unreachable_pairscount andremaining_nodesusing the size of the component just found. - Mark all nodes in the component as visited.
- Continue until all nodes are visited.
public long countUnreachablePairs(int n, int[][] edges) { List<Integer>[] adj = new ArrayList[n]; for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); } for (int[] edge : edges) { adj[edge[0]].add(edge[1]); adj[edge[1]].add(edge[0]); } long unreachablePairs = 0; long remainingNodes = n; boolean[] visited = new boolean[n]; for (int i = 0; i < n; i++) { if (!visited[i]) { long currentComponentSize = 0; Queue<Integer> queue = new LinkedList<>(); queue.offer(i); visited[i] = true; currentComponentSize++; while (!queue.isEmpty()) { int u = queue.poll(); for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; currentComponentSize++; queue.offer(v); } } } unreachablePairs += currentComponentSize * (remainingNodes - currentComponentSize); remainingNodes -= currentComponentSize; } } return unreachablePairs;}Complexity
Time
O(N + E). Building the adjacency list takes O(N + E). The main loop and the traversals together visit each node and edge exactly once.
Space
O(N + E), where N is the number of nodes and E is the number of edges. The adjacency list requires O(N + E) space. The `visited` array and the queue for BFS require O(N) space.
Trade-offs
Pros
Efficient and guaranteed to pass within the time limits.
Conceptually clear, linking the problem to the fundamental graph concept of connected components.
Cons
Requires more space than a Union-Find approach, as the adjacency list can be large if E is large.
This approach uses a Disjoint Set Union (DSU) or Union-Find data structure, which is highly optimized for problems involving connected components or partitioning a set into disjoint subsets. It offers better space complexity than the traversal-based approach.
Algorithm
- Create a
UnionFindclass withfindandunionoperations, including optimizations like path compression and union by size/rank. - Initialize a
UnionFindinstance fornnodes. - Iterate through all
edgesand calluf.union(u, v)for each edge. - Initialize
unreachable_pairs = 0andremaining_nodes = n. - Create a
visitedRootsboolean array to avoid double-counting components. - Iterate through each node
ifrom0ton-1. - Find the root of the component for node
i. - If this root has not been processed yet:
- Get the size of this component from the
UnionFindstructure. - Add
component_size * (remaining_nodes - component_size)tounreachable_pairs. - Subtract
component_sizefromremaining_nodes. - Mark the root as visited.
- Get the size of this component from the
- Return
unreachable_pairs.
Walkthrough
The Union-Find data structure maintains a collection of disjoint sets. We can use it to efficiently group all connected nodes. The algorithm is as follows:
- Initialize a Union-Find structure with
nnodes, where each node is its own parent (i.e.,nseparate components). We also maintain an array to store the size of each component, initially 1 for all. - Iterate through each edge
[u, v]in theedgesarray. - For each edge, call the
unionoperation on nodesuandv. This operation finds the sets thatuandvbelong to and merges them if they are different. When merging, the size of the new combined set is updated. - After processing all edges, the DSU structure correctly represents the connected components. The nodes with the same root belong to the same component.
- We can then find the size of each unique component. One way is to iterate through all nodes
i, find their rootp = find(i), and use a map to store the size of the component rooted atp. The size is available from our size array at indexp. - Once we have a list of all component sizes, we use the same combinatorial logic as the previous approach to calculate the total number of unreachable pairs.
class UnionFind { private int[] parent; private int[] size; public UnionFind(int n) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } } public int find(int i) { if (parent[i] == i) { return i; } return parent[i] = find(parent[i]); // Path compression } public void union(int i, int j) { int rootI = find(i); int rootJ = find(j); if (rootI != rootJ) { // Union by size if (size[rootI] < size[rootJ]) { parent[rootI] = rootJ; size[rootJ] += size[rootI]; } else { parent[rootJ] = rootI; size[rootI] += size[rootJ]; } } } public int getSize(int i) { return size[find(i)]; }} public long countUnreachablePairs(int n, int[][] edges) { UnionFind uf = new UnionFind(n); for (int[] edge : edges) { uf.union(edge[0], edge[1]); } long unreachablePairs = 0; long remainingNodes = n; boolean[] visitedRoots = new boolean[n]; for (int i = 0; i < n; i++) { int root = uf.find(i); if (!visitedRoots[root]) { long componentSize = uf.getSize(root); unreachablePairs += componentSize * (remainingNodes - componentSize); remainingNodes -= componentSize; visitedRoots[root] = true; } } return unreachablePairs;}Complexity
Time
O(N + E * α(N)), where α(N) is the Inverse Ackermann function. This function grows extremely slowly, so the complexity is nearly linear, i.e., O(N + E).
Space
O(N). The `parent` and `size` arrays in the Union-Find structure each require O(N) space. This is more space-efficient than the adjacency list approach if E is large.
Trade-offs
Pros
Most efficient approach in terms of both time and space.
Optimal space complexity of O(N).
The Union-Find data structure is perfectly suited for this type of connectivity problem.
Cons
The Union-Find data structure might be less familiar to some than standard graph traversals.
Solutions
Solution
class Solution {private List<Integer>[] g;private boolean[] vis;public long countPairs(int n, int[][] edges) { g = new List[n]; vis = new boolean[n]; Arrays.setAll(g, i->new ArrayList<>()); for (var e : edges) { int a = e[0], b = e[1]; g[a].add(b); g[b].add(a); } long ans = 0, s = 0; for (int i = 0; i < n; ++i) { int t = dfs(i); ans += s * t; s += t; } return ans; }private int dfs(int i) { if (vis[i]) { return 0; } vis[i] = true; int cnt = 1; for (int j : g[i]) { cnt += dfs(j); } return cnt; }}class Solution {public: long long countPairs(int n, vector<vector<int>> &edges) { vector<int> g[n]; for (auto &e : edges) { int a = e[0], b = e[1]; g[a].push_back(b); g[b].push_back(a); } bool vis[n]; memset(vis, 0, sizeof(vis)); function<int(int)> dfs = [&](int i) { if (vis[i]) { return 0; } vis[i] = true; int cnt = 1; for (int j : g[i]) { cnt += dfs(j); } return cnt; }; long long ans = 0, s = 0; for (int i = 0; i < n; ++i) { int t = dfs(i); ans += s * t; s += t; } return ans; }};class Solution: def countPairs(self, n: int, edges: List[List[int]]) -> int: def dfs(i: int) -> int: if vis[i]: return 0 vis[i] = True return 1 + sum(dfs(j) for j in g[i]) g = [[] for _ in range(n)] for a, b in edges: g[a]. append(b) g[b]. append(a) vis = [False] * n ans = s = 0 for i in range(n): t = dfs(i) ans += s * t s += t return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.