UNIT 01显式与隐式图
#1971 寻找图中是否存在路径
- 节点与边
- 节点是编号顶点，边是输入的无向连接。
- 前沿与更新
- 从起点用栈或队列扩展未访问邻居。
- 维护的关系
- 已发现节点都从起点可达，未发现节点尚不能断言可达。
- 边界检查
- 起终点相同、孤立点与重复边；发现时标记可避免重复加入。
迁移 · #841 钥匙和房间钥匙和房间变成有向邻居关系，结果改为是否访问全部房间。
先说清契约，再独立实现进入本单元 ↗
第8章｜图与并查集
Unit 00 · 图、遍历、连通性、拓扑与并查集基础
仅本次页面有效
U00
Graph & Union-Find FundamentalsVertex · Edge · Frontier · Component · Parent
图算法不是“背 DFS 和 BFS”，
而是先确定节点、边与正在维护的关系。
本单元先把图的语言、邻接表、显式图与隐式图、DFS/BFS、visited、连通分量、环、拓扑排序、并查集与最小生成树一次梳理清楚。后续每道题都会回到同一组问题：节点是什么？边如何生成？搜索前沿是什么？哪个不变量必须始终成立？
检测到上次学习进度阶段、动画、问题、代码、迁移槽位、编辑器高度和滚动位置均可恢复。
Unit 00 提前清除后续图题的术语障碍
- 图语言：节点、边、方向、权重、路径、环、连通分量与度；
- 图表示：边数组、邻接表、邻接矩阵、网格与状态空间；
- 图遍历：DFS 栈、BFS 队列、层、visited、parent 与搜索树；
- 更高层结构：拓扑排序、并查集、路径压缩、按大小合并与最小生成树。
贯穿本章的图建模模板
节点是什么？
边在什么条件下存在？
边是否有方向、权重？
搜索前沿用 stack / queue / heap？
visited 在何时写入？
结果依赖可达、距离、分量、顺序还是连通代价？
Graph Model
同一个输入可以被解释成不同的图。算法之前先明确节点、边、方向、权值与邻居生成规则。
Frontier
栈、队列或优先队列保存“已经发现但尚未处理”的节点，它决定搜索顺序。
State Contract
visited、indegree、color、parent 和 size 都有明确语义；动画会持续检查这些语义是否被破坏。
Connectivity
DFS/BFS 从一个起点探索连通关系；并查集在边动态加入时维护集合归属。
CHAPTER 08 / THE COGNITIVE ATLAS
第 8 章 · 认知梯度全景图
图与并查集：从遍历到连通性，理解图上的关系与依赖。
贯穿本章的统一框架节点是什么 → 边如何产生 → 前沿用什么结构 → 维护可达、距离、依赖还是连通关系。
从基础到复合任务，每一步增加一种决策
这里的梯度描述认知任务的递进，不等同于题库的难度标签。点击题目可进入对应单元。
起点 · Unit 00 图、遍历与并查集基础。先理解状态、操作与不变量，再沿下列路线练习。
- 01
- 02
- 03
- 04
- 05
目录中的 Unit 08 实际为动态规划 #62 的跨章资料。#785 判断二分图目前没有独立 HTML；下面提供其框架定位，不把 #62 当作二分图入口。
每道题在框架中的具体形式
用同一组问题定位每个单元，再观察迁移题改变了哪个条件。进入写代码环节后，学习地图会收起，留出独立思考的空间。
UNIT 02显式与隐式图
#733 图像渲染
- 节点与边
- 节点是像素，只连接相邻且颜色等于原始颜色的格子。
- 前沿与更新
- 从指定像素扩展，染色后再继续处理其邻居。
- 维护的关系
- 前沿中的像素已被标记，原始颜色在搜索中保持固定。
- 边界检查
- 新旧颜色相同时需直接处理，避免无法区分访问状态。
迁移 · #695 岛屿的最大面积岛屿最大面积沿连通搜索累计格子数量，并比较不同分量。
先说清契约，再独立实现进入本单元 ↗
UNIT 03显式与隐式图
#200 岛屿数量
- 节点与边
- 节点是陆地格，边是四方向陆地相邻。
- 前沿与更新
- 扫描网格，遇到未访问陆地就启动一次分量遍历。
- 维护的关系
- 同一陆地分量只被计数一次。
- 边界检查
- 海水不参与连通；不能使用对角相邻代替四方向。
迁移 · #130 被围绕的区域被围绕区域先从边界 O 保护安全分量，再修改内部不安全区域。
先说清契约，再独立实现进入本单元 ↗
UNIT 04身份与层次
#133 克隆图
- 节点与边
- 节点对象是身份，边是 neighbors 引用。
- 前沿与更新
- 首次发现原节点即创建并登记副本，再扩展和翻译邻居。
- 维护的关系
- 每个原节点恰有一个副本，所有新边只连接副本。
- 边界检查
- 自环、环和共享邻居；不能用节点值代替对象身份。
迁移 · #138 随机链表的复制随机链表把通用邻接列表换成 next 与 random 两种引用。
先说清契约，再独立实现进入本单元 ↗
UNIT 05身份与层次
#994 腐烂的橘子
- 节点与边
- 节点是非空橘子格，边是四方向接触。
- 前沿与更新
- 全部腐烂橘子同时作为源，用队列逐层感染新鲜橘子。
- 维护的关系
- 首次被感染的层给出最早感染时间，新鲜数量同步减少。
- 边界检查
- 原本无新鲜橘子为零时间，有不可达新鲜橘子则失败。
迁移 · #542 01 矩阵01 矩阵把所有零格作为源，为每个格记录最近源距离。
先说清契约，再独立实现进入本单元 ↗
UNIT 06依赖与最短路
#207 课程表
- 节点与边
- 节点是课程，有向边由先修课指向依赖它的课程。
- 前沿与更新
- 零入度课程进入前沿，处理后释放它的出边依赖。
- 维护的关系
- 入度表示来自未处理课程的剩余依赖数量。
- 边界检查
- 处理数量少于总课程数意味着有环；孤立课程也须计入。
迁移 · #802 找到最终的安全状态安全状态使用反向边与出度消除，从终点向前传播安全性。
先说清契约，再独立实现进入本单元 ↗
UNIT 07依赖与最短路
#210 课程表 II
- 节点与边
- 课程依赖图，以及已生成的课程顺序。
- 前沿与更新
- 每取出零入度课程就追加到顺序，再释放后继。
- 维护的关系
- 输出前缀中的每门课程，其先修课已经输出。
- 边界检查
- 拓扑顺序可能不唯一，有环时不能返回不完整顺序。
迁移 · #2115 从给定原材料中找到所有可以做出的菜菜谱把课程换成资源与产品，已有原料是最初可用前沿。
先说清契约，再独立实现进入本单元 ↗
UNIT 08跨章资料 · 动态规划
#62 不同路径
- 节点与边
- 跨章资料：网格格子是状态，只能从上方或左方进入。
- 前沿与更新
- 按行列依赖顺序累计到达当前格子的路径数量。
- 维护的关系
- 读取当前格之前，其上方和左方路径数量已经正确。
- 边界检查
- 这是 #62 不同路径，不是 #785 二分图；图题目录中的跨章补充。
迁移 · #63 不同路径 II带障碍网格把被阻断格子的路径数量置为零。
先说清契约，再独立实现进入本单元 ↗
UNIT 09依赖与最短路
#127 单词接龙
- 节点与边
- 单词是节点，相差一个字符且在词库中即有边。
- 前沿与更新
- BFS 按层扩展可达的新单词，首次抵达目标给出最短转换长度。
- 维护的关系
- 队列层次表示已经走过的最少转换次数。
- 边界检查
- 目标不在词库、起点长度和答案的单词数计量。
迁移 · #433 最小基因变化最小基因变化替换字符集与词库，答案计量通常为变化次数。
先说清契约，再独立实现进入本单元 ↗
UNIT 10等价类与动态连通
#547 省份数量
- 节点与边
- 城市是节点，矩阵中的连接表示无向边。
- 前沿与更新
- 遍历计数分量，或用并查集合并边两端所属集合。
- 维护的关系
- 同一集合中的城市通过已处理连接可互达。
- 边界检查
- 对角项不是新增分量，重复连接不能再次减少分量数。
迁移 · #1319 连通网络的操作次数连通网络先检查边总数是否足够，再用分量数计算需要的连接。
先说清契约，再独立实现进入本单元 ↗
UNIT 11等价类与动态连通
#684 冗余连接
- 节点与边
- 节点集合与按输入顺序到达的无向边。
- 前沿与更新
- 两端不同根就合并，相同根说明新边在当前图中形成环。
- 维护的关系
- 每个根代表一个连通分量，接受的边维持无环森林。
- 边界检查
- 已连通不代表直接相邻；只能因有效合并减少分量。
迁移 · #990 等式方程的可满足性等式可满足先合并相等关系，再验证所有不等关系。
先说清契约，再独立实现进入本单元 ↗
UNIT 12等价类与动态连通
#721 账户合并
- 节点与边
- 账户或邮箱组成节点，共享邮箱形成连接。
- 前沿与更新
- 按共享身份合并，再按最终根汇集邮箱。
- 维护的关系
- 传递连通关系汇入同一实体，不能只做直接配对。
- 边界检查
- 相同姓名不必是同一人，邮箱需去重并按输出要求排序。
迁移 · #1202 交换字符串中的元素可交换索引构成分量，每个分量内字符可以重新分配到有序位置。
先说清契约，再独立实现进入本单元 ↗
UNIT 13连通代价
#1584 连接所有点的最小费用
- 节点与边
- 点是节点，完全图边权是曼哈顿距离。
- 前沿与更新
- 按权从小到大考虑边，只接受连接不同分量的边。
- 维护的关系
- 已接受边是无环森林，并以安全的跨分量边逐步连接全部点。
- 边界检查
- 选够 n−1 条边即可；单点不需要连接费用。
迁移 · #1631 最小体力消耗路径最小体力路径累计的是最大边权阈值，而非生成树边权总和。
先说清契约，再独立实现进入本单元 ↗
拓展定位配色约束
#785 判断二分图
- 节点与边
- 节点是顶点，无向边要求两端属于不同组。
- 前沿与更新
- 从每个未着色分量启动 DFS 或 BFS，给邻居分配相反颜色。
- 维护的关系
- 每条已经检查的边两端颜色不同，已赋色节点不能随意改色。
- 边界检查
- 不连通图须启动多个源；遇到同色相邻节点即产生冲突。
独立训练页面待补充
目录中的 Unit 08 实际为动态规划 #62 的跨章资料。#785 判断二分图目前没有独立 HTML；下面提供其框架定位，不把 #62 当作二分图入口。
认知任务 1
先决定节点和边，再选择算法
同一组数据可以被建模为无向图、有向图、带权图或隐式图。切换实验并观察邻接关系如何改变。
图模型实验台状态 1 / 5
先观察当前图的节点、边与邻接关系。
BFS 最短路径：补全 5 个关键表达式邻接表 + queue + visited + parent
from collections import deque
from typing import List
def shortest_path(n: int, edges: List[List[int]],
source: int, destination: int) -> List[int]:
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[].append()
queue = deque([source])
visited = {}
parent = {source: None}
while queue:
node = queue.popleft()
if node == destination:
break
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] =
queue.(neighbor)
if destination not in parent:
return []
path = []
node = destination
while node is not None:
path.append(node)
node = parent[node]
return path[::-1]
真实运行轨迹步骤 1 / 12
queue
visited
parent
当前结果
LeetCode #1971｜寻找图中是否存在路径
给定一个含有 n 个顶点的双向图，顶点编号为 0 到 n - 1。二维数组 edges 中的每个 [u, v] 表示顶点 u 和 v 之间存在一条双向边。
给定 source 和 destination，判断是否存在从源点到目标点的有效路径。存在则返回 True，否则返回 False。
示例 1 输入：n = 3 edges = [[0,1],[1,2],[2,0]] source = 0, destination = 2 输出：true 示例 2 输入：n = 6 edges = [[0,1],[0,2],[3,5],[5,4],[4,3]] source = 0, destination = 5 输出：false
1 <= n <= 2 * 10^50 <= edges.length <= 2 * 10^5- 每条边连接两个不同顶点；不存在重复边和自环。
source、destination均在合法编号范围内。
Python 签名：def validPath(self, n, edges, source, destination) -> bool
迁移目标不是“重新写一遍 BFS”
Unit 00 的代码实验返回完整最短路径；#1971 只需要判断可达。迁移时应先识别哪些状态可以删除，而不是从空白编辑器重新发明整个算法。
| 当前实验 | #1971 |
|---|---|
| 返回节点路径 | 返回布尔值 |
| 需要 parent | 不需要 parent |
| 到达目标后重建路径 | 到达目标立即 True |
| 前沿耗尽返回 [] | 前沿耗尽返回 False |
阶段 1 / 6 · 可随时点击顶部导航返回任意环节
第八章 Unit 00 · 最终 Skill 卡
看到新题时，先填完下面的模型，再决定使用 DFS、BFS、拓扑排序、并查集、最小生成树或带权路径算法。
Graph Model节点、边、方向、权重与邻居生成规则
Traversal Statefrontier、visited、parent、layer 与停止条件
Connectivity一次搜索覆盖一个分量；并查集维护动态集合
Dependency入度为 0 的节点可被处理；剩余节点意味着环
Union-Find Contractfind(a) == find(b) 等价于处于同一集合
Complexity图遍历 O(V+E)；明确 V 和 E 在当前题中的含义
完成后仍停留在当前页面
页面不会倒计时或自动跳转。可以返回任意环节复盘动画，也可以继续完善迁移代码。