题目描述
思路解析动画文字版
记牢这一句:一块连通分量,顶点数是 x、度数和是 y,只要 x 乘以 x 减 1 等于 y,它就是完全分量。用度数和来判,省得单独去数边、也不怕重复。下面从顶点 0 开始,一块一块地走。
先看整张图 · 三块相连的顶点：这是我们要处理的图。一眼看去,顶点自然分成三块:左边 0、1、2 三个点两两连着,像个三角形;中间 3、4、5,3 分别连到 4 和 5,可 4 和 5 之间是断开的;右边 6 是个光杆,一条边都没有。这三块就是三个连通分量,接下来逐块检验它们完不完全。
什么叫完全 · 每对顶点都要有边：先把完全的判据说清。一块有 x 个顶点,要让它们两两之间都直接有边,一共需要 x 乘以 x 减 1 再除以 2 条边。1 个点不需要边,天生完全;2 个点要 1 条边;3 个点要 3 条边,也就是凑成一个三角形。等会儿每走完一块,就拿它实际的边数和这个应有的边数比一比。
巧劲 · 用度数和代替数边：这里有个省事的巧劲。与其小心翼翼地数边,不如把块里每个顶点的度数加起来,记成 y。因为每条边连着两个端点,会在两个端点的度数里各被算一次,所以 y 刚好是边数的 2 倍。这么一来,完全的条件从「边数等于 x 乘 x 减 1 除以 2」直接变成「y 等于 x 乘 x 减 1」,遍历时顺手就把 y 累出来了。
外层扫描 · 找未访问的起点：整体框架是这样:外层用 i 从 0 扫到 6,一旦碰到一个还没被访问过的顶点,就以它为起点发起一次深度优先遍历,把它所在的一整块分量走遍,同时把这块的 x 和 y 累出来。走过的点随手标记已访问,外层就不会重复进同一块。下面开始扫。
发现分量一 · 起点 0：外层从 0 开始,0 还没访问过,就以它为起点发起 DFS。开一个计数:顶点数 x 先记 1,度数和 y 先把 0 的度数加进去。0 连着 1 和 2 两条边,度数是 2,所以 y 现在是 2。0 就是这块分量的第一个顶点。
在 0 上 · 看邻居 1、2：站在 0,把它标成正在处理。看它的邻接表,邻居是 1 和 2,都还没访问。深度优先的规矩是先认准一个邻居钻到底,再回头处理另一个。按建图的顺序,先走去 1。两条从 0 出发的边先点亮,表示待会儿都要走。
沿边 0-1 到 1：顺着边 0-1 走到 1,把它收进这块分量。x 从 1 加到 2。1 也连着两条边,连到 0 和 2,度数是 2,把它加进 y,y 从 2 变成 4。1 这个点先标成刚够到的蓝色,马上轮到处理它。
在 1 上 · 唯一没走的邻居是 2：轮到处理 1。它的邻居是 0 和 2,0 刚才已经访问过了,跳过,只剩 2 还没走。那就沿着边 1-2 继续往下钻。深度优先就是这样一条路走到底,把能连的都串起来。
沿边 1-2 到 2：走到 2,收进分量,x 加到 3。2 连着 0 和 1 两条边,度数是 2,加进 y,y 从 4 变成 6。到这儿这块分量的三个顶点 0、1、2 都收齐了,x 是 3,y 是 6。
在 2 上 · 0 与 2 之间也有边：处理 2 的时候,它的邻居 0 和 1 都访问过了,这块就到头了。注意看,除了走过的 0-1、1-2,0 和 2 之间同样有一条边。也就是说 0、1、2 这三对顶点,每一对都直接连着。这一点度数和已经替我们记下了:y 等于 6。
分量一结算 · 完全分量,答案 +1：这块分量走完,x 是 3、y 是 6。套判据:x 乘以 x 减 1 等于 3 乘 2 等于 6,正好等于 y。等式成立,0、1、2 是一个完全分量。把三个顶点整块涂绿,完全分量数从 0 加到 1。
发现分量二 · 起点 3：外层继续往后扫,1、2 都访问过了,扫到 3,它还没访问,又发起一次 DFS。计数重新开张:x 记 1。3 连着 4 和 5 两条边,度数是 2,y 先记 2。开始走这块新的分量。
在 3 上 · 看邻居 4、5：站在 3,看它的邻居,是 4 和 5,都没访问。按顺序先钻去 4。两条从 3 出发的边先点亮。你先记着一个悬念:3 分别连着 4 和 5,可 4 跟 5 彼此之间有没有边,得走过去才知道。
沿边 3-4 到 4：顺着边 3-4 到 4,收进分量,x 加到 2。可这次不一样:4 只连着 3 这一条边,度数是 1,加进 y 只让 y 从 2 变成 3。度数和涨得慢,已经在暗示这块的边不太够了。
在 4 上 · 4 只连着 3：处理 4,它的邻居只有一个 3,还是已经访问过的。这条路到头了,退回 3。你看,4 这个点是个叶子,除了拴在 3 上,和别人没有任何联系。回到 3 去走它另一个还没走的邻居 5。
沿边 3-5 到 5：回到 3,沿边 3-5 走到 5,收进分量,x 加到 3。5 也一样,只连着 3 这一条边,度数是 1,y 从 3 变成 4。三个顶点 3、4、5 都收齐了,可 x 是 3、y 只有 4。
关键 · 4 与 5 之间没有边：把这块看清楚:3 像个中心,分别拉着 4 和 5,可是 4 和 5 之间空着,没有边。3 个顶点要想两两相连得有 3 条边,凑成三角形,这里只有 3-4、3-5 两条。缺了 4-5 那条,这块就不是完全分量。
分量二结算 · 不完全,不计数：算一下:x 乘以 x 减 1 是 3 乘 2 等于 6,可 y 只有 4,等式不成立。所以 3、4、5 这块不是完全分量,不计数。把它们恢复成常态的灰色,完全分量数还是 1,一个没加。度数和差在哪儿一目了然:少一条边,y 就少 2。
发现分量三 · 起点 6(孤立点)：外层扫到最后一个点 6,它还没访问,发起 DFS。6 是个孤立点,一条边都没有。x 记 1,它的度数是 0,y 就是 0。这块分量只有它自己一个顶点。
在 6 上 · 没有任何邻居：处理 6,它的邻接表是空的,没有邻居可走,这块分量就它一个点,直接结束。x 是 1,y 是 0。别小看这种单点分量,它其实是完全分量里最特殊的一种。
分量三结算 · 单点也是完全,答案 +1：套判据:x 乘以 x 减 1 是 1 乘 0 等于 0,y 也是 0,等式成立。所以单个孤立点 6 也是一个完全分量,因为它里面根本没有「两个顶点」需要相连,判据自动满足。把 6 涂绿,完全分量数从 1 加到 2。
回放 · 两个完全分量,答案 2：三块分量全部查完。0、1、2 三角形每对都连,完全,绿的;6 孤立点没有任何一对要连,也算完全,绿的;3、4、5 缺了 4-5 那条边,不完全,灰的。数一数绿的分量,一共 2 个,这就是答案。判定自始至终只有一句话:x 乘以 x 减 1 等不等于度数和 y。
边界想清:单点算 1 个完全分量、两个孤立点算 2 个、三点成链缺一条边则不完全记 0。
面试重点:逐分量数 x 和度数和 y、判 x 乘 x 减 1 等于 y、可换并查集、复杂度 O(n 加 m)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *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复杂度
- 时间：O(n + m)，n 个顶点 m 条边。建邻接表扫一遍所有边是 O(m);DFS 阶段每个顶点恰好被访问一次、每条边在两个端点各被看一次,合起来是 O(n + m)。整体随顶点数加边数线性增长
- 空间：O(n + m)，按峰值算。邻接表存了每条边的两个方向,占 O(n + m);vis 数组 O(n);递归栈最坏在一条链状分量铺满时到 O(n)。峰值是 O(n + m)
易错点
面试追问把动画讲成自己的话
追问这题的核心判定是什么?
追问为什么用度数和而不去数边?
追问除了 DFS 还能怎么做,复杂度多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
单词接龙 II
LeetCode 126 · 困难 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题