Count Unreachable Pairs of Nodes in an Undirected Graph

MEDIUM

Description

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.

Approaches

Checkout 3 different approaches to solve Count Unreachable Pairs of Nodes in an Undirected Graph. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Pairwise Reachability Check

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.

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 Analysis

Time Complexity: 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 Complexity: O(N + E). O(N + E) for the adjacency list and O(N) for the `visited` array and queue/stack used in each traversal.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Count Unreachable Pairs of Nodes in an Undirected Graph. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Count Unreachable Pairs of Nodes in an Undirected Graph

Algorithms:

Depth-First SearchBreadth-First SearchUnion Find

Data Structures:

Graph

Companies:

Commvault |