Design Gurus Logo
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)

Problem Statement

You are given a positive integer n. You are also given undirected graph containing 0 to n - 1 nodes, and 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes a<sup>i</sup> and b<sup>i</sup>.

Return the count of unique node pairs where there's no path from one node to another.

Examples

Example 1:

  • Input: n = 4, edges = [[0, 1], [2, 3]]
Image
  • Expected Output: 4
  • Justification: The graph is divided into two disconnected parts: nodes 0 and 1 are connected, and nodes 2 and 3 are connected. The unreachable pairs are (0, 2), (0, 3), (1, 2), and (1, 3).

Example 2:

  • Input: n = 5, edges = [[0, 1], [2, 3]]
Image
  • Expected Output: 8
  • Justification: The unreachable pairs are (0, 2), (0, 3), (1, 2), (1, 3), (0, 4), (1, 4), (2, 4), and (3, 4).

Example 3:

  • Input: n = 3, edges = []
  • Expected Output: 3
  • Justification: With no edges, every node is isolated. Hence, all possible pairs are unreachable from each other: (0, 1), (0, 2), and (1, 2).

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Unlock this and all other premium problems.
No code editor for this lesson
This lesson focuses on concepts and theory