LeetCode 2316 - Count Unreachable Pairs of Nodes in an Undirected Graph

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

Solution

Problem Understanding

The problem asks us to find the number of pairs of nodes in an undirected graph that cannot reach each other via any path. You are given an integer n representing the total number of nodes labeled from 0 to n - 1 and a list of edges representing connections between nodes. Each edge is bidirectional. The output should be a single integer: the total count of unordered node pairs (i, j) such that there is no path connecting node i to node j.

This problem essentially asks us to identify connected components in the graph, because nodes that belong to the same connected component can reach each other, while nodes from different components cannot. The number of unreachable pairs can then be calculated from the sizes of these components.

Constraints indicate that n can be as large as 10^5 and the number of edges can be up to 2 * 10^5. This rules out any solution that requires checking connectivity for every pair of nodes individually since that would be O(n^2), which is infeasible.

Important edge cases include:

A completely connected graph, where all nodes are reachable from each other, resulting in 0 unreachable pairs.
A graph with no edges, where all pairs of nodes are unreachable.
Graphs with multiple small disconnected components, which must be carefully combined to count pairs correctly.

Approaches

The brute-force approach would involve iterating over all possible pairs of nodes and performing a BFS or DFS for each pair to check if there is a path connecting them. While this guarantees correctness, its time complexity is O(n^2) multiplied by the traversal cost of O(n + m), which is prohibitively expensive for the input limits (n up to 10^5).

The optimal approach leverages the key observation that the graph can be divided into connected components. If we know the size of each component, we can calculate the number of unreachable pairs as the sum of all products of sizes of different components. Alternatively, we can iterate through components and compute the number of unreachable pairs using a running total formula: if size_so_far is the total number of nodes counted in previous components, then for the current component of size sz, the number of new unreachable pairs contributed is sz * (n - size_so_far - sz). This approach requires one traversal to find components and then simple arithmetic to compute the answer, making it efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2 * (n + m))	O(n + m)	Check each pair for connectivity using DFS/BFS
Optimal	O(n + m)	O(n + m)	Find connected components and compute unreachable pairs

Algorithm Walkthrough

Initialize a graph as an adjacency list to store all connections. This allows O(1) access to neighbors during traversal.
Create a visited array of size n initialized to False. This keeps track of nodes already included in a component.
Iterate through each node i from 0 to n-1. If a node is not visited, start a DFS or BFS from it to explore its connected component.
For each traversal, count the number of nodes sz in the component and mark them visited.
Maintain a running total seen to accumulate the number of nodes already processed in previous components.
For the current component of size sz, calculate the number of new unreachable pairs as sz * (n - seen - sz) and add it to the total answer.
Update seen by adding sz to it.
Return the total count after processing all components.

Why it works: By counting the size of each connected component, we know exactly how many nodes are mutually reachable. Any node outside a given component is unreachable from nodes inside the component. The arithmetic guarantees that all pairs are counted once without repetition.

Python Solution

from typing import List
from collections import defaultdict, deque

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        visited = [False] * n
        
        def bfs(start: int) -> int:
            queue = deque([start])
            visited[start] = True
            size = 1
            while queue:
                node = queue.popleft()
                for neighbor in graph[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)
                        size += 1
            return size
        
        total_pairs = 0
        seen = 0
        for node in range(n):
            if not visited[node]:
                component_size = bfs(node)
                total_pairs += component_size * (n - seen - component_size)
                seen += component_size
                
        return total_pairs

The Python code first constructs the adjacency list from the edge list. BFS is used to compute the size of each connected component, marking nodes visited. For each component, the formula size * (n - seen - size) counts all pairs that are unreachable from this component, avoiding double counting. The final answer is accumulated in total_pairs.

Go Solution

package main

func countPairs(n int, edges [][]int) int64 {
    graph := make([][]int, n)
    for _, e := range edges {
        u, v := e[0], e[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }
    
    visited := make([]bool, n)
    
    var bfs func(int) int
    bfs = func(start int) int {
        queue := []int{start}
        visited[start] = true
        size := 1
        for len(queue) > 0 {
            node := queue[0]
            queue = queue[1:]
            for _, neighbor := range graph[node] {
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue = append(queue, neighbor)
                    size++
                }
            }
        }
        return size
    }
    
    var totalPairs int64 = 0
    seen := 0
    for i := 0; i < n; i++ {
        if !visited[i] {
            componentSize := bfs(i)
            totalPairs += int64(componentSize) * int64(n - seen - componentSize)
            seen += componentSize
        }
    }
    
    return totalPairs
}

In Go, slices and int64 are used to safely handle large numbers. BFS logic is identical to Python, but queue operations are manually managed using slice appends and slicing.

Worked Examples

Example 2: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]

Components discovered: [0,2,4,5] size 4, [1,6] size 2, [3] size 1.
Running totals:

Component	Size	Seen before	New Pairs
[0,2,4,5]	4	0	4 * (7 - 0 - 4) = 12
[1,6]	2	4	2 * (7 - 4 - 2) = 2
[3]	1	6	1 * (7 - 6 - 1) = 0

Total unreachable pairs = 12 + 2 + 0 = 14

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Constructing adjacency list O(m), traversing each node once O(n), visiting all edges O(m)
Space	O(n + m)	Adjacency list O(n + m), visited array O(n), BFS queue O(n)

This linear complexity is efficient and fits within the given constraints.

Test Cases

# Provided examples
assert Solution().countPairs(3, [[0,1],[0,2],[1,2]]) == 0  # fully connected
assert Solution().countPairs(7, [[0,2],[0,5],[2,4],[1,6],[5,4]]) == 14  # multiple components

# Edge cases
assert Solution().countPairs(1, []) == 0  # single node
assert Solution().countPairs(5, []) == 10  # no edges, all pairs unreachable
assert Solution().countPairs(4, [[0,1],[2,3]]) == 4  # two pairs of connected components

Test	Why
`n = 3, edges=[[0,1],[0,2],[1,2]]`	Validates fully connected graph
`n = 7, edges=[[0,2],[0,5],[2,4],[1,6],[5,4]]`	Validates multiple components
`n = 1, edges=[]`	Single node edge case
`n = 5, edges=[]`	All nodes disconnected
`n = 4, edges=[[0,1],[2,3]]`	Two small components

Edge Cases

One important edge case is a graph with no edges. Here, each node forms its own component of size 1,