Scale Engineer

Count Unreachable Pairs of Nodes in an Undirected Graph

Med
#2110Time: 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.1 company
Algorithms
Depth-First SearchBreadth-First SearchUnion Find
Data structures
Graph
Companies
Commvault

Prompt

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 <= 105
  • 0 <= edges.length <= 2 * 105
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != 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 i from 0 to n-1.
  • Inner loop for j from i+1 to n-1.
  • Inside the inner loop, call a function areConnected(i, j) which performs a BFS/DFS starting from i.
  • If areConnected returns false, increment unreachable_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.

Solutions

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;  }}

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

← Previous

Previous problem

Next →

Next problem