We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Unreachable Pairs of Nodes in an Undirected Graph

Difficulty: Medium

Problem 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] = [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.

Key Insights

  • The graph is undirected, meaning if there is an edge between two nodes, both nodes can reach each other.
  • Unreachable pairs of nodes are those that belong to separate connected components of the graph.
  • The number of unreachable pairs can be calculated by determining the sizes of each connected component and using combinatorial mathematics.

Space and Time Complexity

Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges. This is due to the traversal of the graph using either DFS or BFS. Space Complexity: O(n), for storing the graph structure and visited nodes.

Solution

To solve the problem, we can represent the graph using an adjacency list. We will then perform a graph traversal (either Depth-First Search or Breadth-First Search) to find all connected components. For each component, we will count how many nodes it contains. The number of unreachable pairs can be calculated using the sizes of the connected components: if a component has size size_i, then it can form size_i * (total_nodes - size_i) pairs with nodes from other components. We will sum these counts for all components to get the final result.

Code Solutions

def countUnreachablePairs(n, edges):
    from collections import defaultdict
    
    # Create an adjacency list
    graph = defaultdict(list)
    
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    
    visited = [False] * n
    component_sizes = []
    
    def dfs(node):
        stack = [node]
        size = 0
        while stack:
            current = stack.pop()
            if not visited[current]:
                visited[current] = True
                size += 1
                for neighbor in graph[current]:
                    if not visited[neighbor]:
                        stack.append(neighbor)
        return size
    
    # Find all connected components
    for i in range(n):
        if not visited[i]:
            component_size = dfs(i)
            component_sizes.append(component_size)
    
    # Calculate unreachable pairs
    total_pairs = 0
    total_nodes = sum(component_sizes)
    
    for size in component_sizes:
        total_pairs += size * (total_nodes - size)
    
    # Each pair is counted twice (u, v) and (v, u)
    return total_pairs // 2
← Back to All Questions