#2316

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Count Unreachable Pairs of Nodes in an Undirected Graph

Calculate the total number of node pairs in an undirected graph that cannot reach each other using DFS, BFS, or Union Find.

depth first search breadth first search union find graph

Problem Statement

Given an integer n representing nodes numbered from 0 to n - 1, and a list of undirected edges where each edge connects two distinct nodes, determine how many pairs of nodes cannot reach each other through any path. The graph may be disconnected and have no repeated edges.

Return an integer representing the total number of node pairs that are unreachable from each other. For example, with n = 7 and edges = [[0,2],[0,5],[2,4],[1,6],[5,4]], the output is 14 because there are 14 pairs of nodes that cannot reach one another.

Examples

Example 1

Input: n = 3, edges = [[0,1],[0,2],[1,2]]

Output: 0

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

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 <= 105
0 <= edges.length <= 2 * 105
edges[i].length == 2
0 <= ai, bi < n
ai != bi
There are no repeated edges.

Solution Approach

Identify Connected Components

Use DFS, BFS, or Union Find to traverse the graph and determine connected components. Track the size of each component to avoid revisiting nodes and efficiently capture all groupings.

Count Pairs Across Components

For each component, calculate the number of unreachable pairs by multiplying its size with the total number of nodes not in that component. Sum these results to get the final count, avoiding double-counting by careful aggregation.

Optimize for Large Graphs

Since n can be up to 10^5, avoid O(n^2) approaches. Use component sizes and prefix sums to calculate total unreachable pairs in linear time relative to the number of nodes and edges.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on traversal: O(n + m) using DFS/BFS or Union Find, where n is nodes and m is edges. Space complexity is O(n + m) for adjacency lists and O(n) for tracking visited nodes or component parents.

What Interviewers Usually Probe

Check if the candidate identifies that the graph may be disconnected.
Watch if DFS, BFS, or Union Find is applied correctly to count connected components.
See if the candidate multiplies component sizes instead of iterating all pairs to avoid TLE.

Common Pitfalls or Variants

Common pitfalls

Counting all pairs without considering component separation leads to wrong answers and TLE.
Failing to mark visited nodes can double-count pairs or miss components.
Assuming a connected graph ignores disconnected components and undercounts unreachable pairs.

Follow-up variants

Return unreachable pairs in a directed graph with similar DFS/BFS strategies.
Count unreachable triplets of nodes instead of pairs, using combinatorial sums of component sizes.
Handle dynamic graph updates where edges are added or removed and track unreachable pairs incrementally.

FAQ

How do I find unreachable pairs in an undirected graph?

Identify connected components using DFS, BFS, or Union Find, then multiply component sizes to count all pairs that cannot reach each other.

Can I use BFS instead of DFS for this problem?

Yes, BFS works equivalently to DFS to explore components and compute sizes, giving the same unreachable pair counts.

Why can't I just check every pair of nodes?

Checking all pairs is O(n^2), which is too slow for large n. Using component sizes reduces the complexity to O(n + m).

Does Union Find offer any advantage here?

Union Find efficiently merges connected nodes and tracks component sizes without explicit recursion, saving time and stack space on large graphs.

What pattern does this problem use in GhostInterview?

It follows the graph traversal with depth-first search pattern, focusing on connected component identification and unreachable pair counting.

terminal

Solution

Solution 1: DFS

For any two nodes in an undirected graph, if there is a path between them, then they are mutually reachable.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        def dfs(i: int) -> int:
            if vis[i]:
                return 0
            vis[i] = True
            return 1 + sum(dfs(j) for j in g[i])

        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        vis = [False] * n
        ans = s = 0
        for i in range(n):
            t = dfs(i)
            ans += s * t
            s += t
        return ans

Continue Practicing

#2368 reachable nodes with restrictions #2492 minimum score of a path between two cities #2493 divide nodes into the maximum number of groups