LeetCode Solutions Blog

Count Unreachable Pairs of Nodes in an Undirected Graph

Number: 2403

Difficulty: Medium

Paid? No

Problem Description

Given an undirected graph with n nodes (labeled from 0 to n - 1) and a list of edges, count the number of pairs of nodes that are unreachable from each other.

Key Insights

The graph may consist of several connected components.
Nodes within the same component are reachable; nodes in different components are not.
The total number of pairs is given by n*(n-1)/2.
Subtract reachable pairs (pairs within the same component) from the total pairs to get the unreachable pairs.
Connected components can be discovered using DFS, BFS, or Union Find.

Space and Time Complexity

Time Complexity: O(n + |edges|)
Space Complexity: O(n + |edges|)

Solution

We first traverse the graph to identify all connected components using a DFS/BFS approach (or Union Find). For each component, we record its size. The number of reachable pairs within a component of size c is c*(c-1)/2. Subtracting the sum of these counts from the total pairs n*(n-1)/2 gives the number of unreachable pairs.

Code Solutions

# Python solution using DFS

def countPairs(n, edges):
    # Build the graph as an adjacency list
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    visited = [False] * n
    
    # Helper function for DFS to compute component size
    def dfs(node):
        stack = [node]
        size = 0
        while stack:
            curr = stack.pop()
            if not visited[curr]:
                visited[curr] = True
                size += 1
                # Add all unvisited neighbors to the stack
                for neighbor in graph[curr]:
                    if not visited[neighbor]:
                        stack.append(neighbor)
        return size

    component_sizes = []
    # Compute sizes for all connected components
    for i in range(n):
        if not visited[i]:
            size = dfs(i)
            component_sizes.append(size)
    
    # Compute total pairs and subtract reachable pairs within each component.
    total_pairs = n * (n - 1) // 2
    reachable_pairs = sum((size * (size - 1) // 2 for size in component_sizes))
    
    return total_pairs - reachable_pairs

# Example usage:
n = 7
edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
print(countPairs(n, edges))  # Output: 14