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.

#2316

Medium

auto_awesome图·DFS·traversal

LeetCode 题解工作台

统计无向图中无法互相到达点对数

给你一个整数 n ，表示一张无向图中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [a i , b i ] 表示节点 a i 和 b i 之间有一条无向边。请你返回无法互相到达的不同点对数目。示例 1：输入： …

深度优先搜索广度优先搜索并查集图

题目描述

给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [a_i, b_i] 表示节点 a_i 和 b_i 之间有一条无向边。

请你返回 无法互相到达 的不同 点对数目 。

示例 1：

输入：n = 3, edges = [[0,1],[0,2],[1,2]]
输出：0
解释：所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。

示例 2：

输入：n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
输出：14
解释：总共有 14 个点对互相无法到达：
[[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]]
所以我们返回 14 。

提示：

1 <= n <= 10⁵
0 <= edges.length <= 2 * 10⁵
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
不会有重复边。

lightbulb

解题思路

方法一：DFS

对于无向图中的任意两个节点，如果它们之间存在一条路径，那么它们之间就是互相可达的。

因此，我们可以通过深度优先搜索的方式，找出每一个连通分量中的节点个数 $t$ ，然后将当前连通分量中的节点个数 $t$ 与之前所有连通分量中的节点个数 $s$ 相乘，即可得到当前连通分量中的不可达点对数目 $s \times t$ ，然后将 $t$ 加到 $s$ 中。继续搜索下一个连通分量，直到搜索完所有连通分量，即可得到答案。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 和 $m$ 分别是节点数和边数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2368 受限条件下可到达节点的数目 #2492 两个城市间路径的最小分数 #2493 将节点分成尽可能多的组