What is a complete connected component in this problem?

A complete connected component is a subset of vertices where every vertex pair is directly connected by an edge, forming a fully connected subgraph.

Can I use BFS instead of DFS to solve Count the Number of Complete Components?

Yes, BFS can traverse the graph in the same way as DFS to identify connected components, allowing you to check completeness afterward.

Why might Union Find be helpful for this problem?

Union Find can efficiently group vertices into components and track connectivity, reducing repeated traversal when verifying completeness.

How do I handle isolated vertices?

Isolated vertices count as complete components of size one since they trivially satisfy the completeness condition.

What is the expected complexity using DFS or BFS?

Using DFS or BFS, the time complexity is O(n + m) and space is O(n), covering all vertices and edges once while checking component completeness.

#2685

Medium

auto_awesome图·DFS·traversal

LeetCode 题解工作台

统计完全连通分量的数量

给你一个整数 n 。现有一个包含 n 个顶点的无向图，顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges 其中 edges[i] = [a i , b i ] 表示顶点 a i 和 b i 之间存在一条无向边。返回图中完全连通分量的数量。如果在子图中任意两个顶点之间…

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

题目描述

给你一个整数 n 。现有一个包含 n 个顶点的无向图，顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges 其中 edges[i] = [a_i, b_i] 表示顶点 a_i 和 b_i 之间存在一条无向边。

返回图中 完全连通分量 的数量。

如果在子图中任意两个顶点之间都存在路径，并且子图中没有任何一个顶点与子图外部的顶点共享边，则称其为 连通分量 。

如果连通分量中每对节点之间都存在一条边，则称其为 完全连通分量 。

示例 1：

输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
输出：3
解释：如上图所示，可以看到此图所有分量都是完全连通分量。

示例 2：

输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
输出：1
解释：包含节点 0、1 和 2 的分量是完全连通分量，因为每对节点之间都存在一条边。
包含节点 3 、4 和 5 的分量不是完全连通分量，因为节点 4 和 5 之间不存在边。
因此，在图中完全连接分量的数量是 1 。

提示：

1 <= n <= 50
0 <= edges.length <= n * (n - 1) / 2
edges[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i
不存在重复的边

lightbulb

解题思路

方法一：DFS

我们先根据题目给定的边建立一个邻接表 $g$ ，其中 $g[i]$ 表示顶点 $i$ 的邻接点集合。

然后我们从 $0$ 开始遍历所有顶点，如果当前顶点没有被访问过，我们就从当前顶点开始进行深度优先搜索，统计当前连通分量的顶点数 $x$ 和边数 $y$ 。如果 $\frac{x(x-1)}{2} = y$ ，那么当前连通分量就是完全连通分量，我们将答案加一。

最后我们返回答案即可。

时间复杂度 $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

21

22

23

24

class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        def dfs(i: int) -> (int, int):
            vis[i] = True
            x, y = 1, len(g[i])
            for j in g[i]:
                if not vis[j]:
                    a, b = dfs(j)
                    x += a
                    y += b
            return x, y

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        vis = [False] * n
        ans = 0
        for i in range(n):
            if not vis[i]:
                a, b = dfs(i)
                ans += a * (a - 1) == b
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n + mα(n)) where n is vertices and m is edges, accounting for Union Find operations. Space complexity is O(n) for tracking visited nodes or parent arrays in Union Find.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Pay attention if the candidate correctly identifies all connected components using DFS or BFS.
question_mark
Check if the solution validates completeness efficiently without redundant edge checks.
question_mark
Watch for proper handling of small graphs and edge cases with single-node components.

warning

常见陷阱

外企场景

error
Forgetting to check every vertex pair in a component can overcount incomplete components.
error
Revisiting nodes without marking them can lead to infinite loops or wrong component counts.
error
Assuming all components with edges are complete without verifying full connectivity within each.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count only components with exactly k vertices that are complete.
arrow_right_alt
Determine the largest complete component in terms of vertex count.
arrow_right_alt
Handle weighted graphs where completeness requires all edges to exceed a threshold weight.

help

常见问题

外企场景

继续练习

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