用邻接表和访问标记，数出连通块
这一课只练一件事：遇到“若干个点、若干条边，问一共分成几组互相连通”这类问题时，用把点和边画出来，用记录每个点连着谁，再用防止重复访问，跑一次或数出数量。必会：能画出小图和邻接关系、能写访问标记、能说明 DFS 与 BFS 的顺序差异。最小示例：5 个点（编号 0~4），边为 (0,1) (1,2) (3,4)，这是无向图，1 <= n <= 1000。样例追踪：邻接表 adj[0]={1}, adj[1]={0,2}, adj[2]={1}, adj[3]={4}, adj[4]={3}；访问标记 visited 全部初始化为 false；从 0 出发 DFS 访问到 {0,1,2}，再从还没访问过的 3 出发 DFS 访问到 {3,4}，连通块数 = 2。边界是没有边的孤立点（自己就是一个连通块）和已经访问过的点（不能再重复计数）。建议掌握：DFS 沿一条路径尽量走到底再回头，BFS 按“一层一层”向外扩展，得到的是离起点的最短步数层级，这两种顺序本质不同。拓展：BFS 求出的层数可以直接当作“最短步数”的初步认识，现在只需要知道概念，不强制要求现在就写完整的最短路模板。这里不会在浏览器里运行 C++。
任务 1：先选出该怎么表示图，怎么防止重复访问
先确定用什么方式记录里“谁和谁相连”，再确定怎么防止 DFS/BFS 重复访问同一个点。点不认识的词可看基础解释。
必会：能说出邻接表怎么保存每个点的邻居；能说出为什么需要。这里不会在浏览器里运行 C++，只练习选择和走过程。
5 个点（0~4），边为 (0,1) (1,2) (3,4)，要频繁查询某点直接相连的点，最合适的表示方式是？图的表示 · 必会
DFS 从 0 出发会经过 0→1→2，如果不记录“谁已经访问过”，可能会发生什么？访问标记 · 必会
任务 2：按邻接表、访问标记、DFS 三步数出连通块
最小示例：5 个点（0~4），边为 (0,1) (1,2) (3,4)，这是无向图。按顺序点三步：先写，再写的初值，最后跑数出。这里不会在浏览器里运行 C++。
必会：能解释每一步为什么这样做。边界：不要跳过“访问标记”直接跑 DFS；从 0 出发只能访问到 {0,1,2}，还要检查有没有未访问的点（比如 3），有就再发起一次 DFS，连通块数才不会漏算。
- // 图：5 个点，边 (0,1) (1,2) (3,4)（无向图）
- // 邻接表：adj[0]={1}, adj[1]={0,2}, adj[2]={1}, adj[3]={4}, adj[4]={3}
- // 访问标记：visited[5] 全部初始化为 false
- // DFS：从 0 出发访问 {0,1,2}；从未访问的 3 出发访问 {3,4} → 连通块数 = 2
三步走完了，现在把“防止重复访问”落成一行代码：dfs 走到一个点 u 时，先看它来过没有——来过就马上结束这次调用，别再往下走。 这种类型只有 true 和 false 两个值，正好用来当访问标记。下面是只读脚手架，只留一空给你敲键盘；这里不会在浏览器里运行 C++。
- // 最小示例：5 个点（0~4），边 (0,1) (1,2) (3,4)，这是无向图
- int adj[1005][1005]; // 邻接表（数组版）：adj[u][k] 是 u 的第 k 个邻居
- int deg[1005]; // deg[u] 记录 u 有几个邻居
- bool visited[1005]; // 访问标记：false 表示还没来过，true 表示来过了
- void dfs(int u) {
- // 来过就收工，别再往下走
- visited[u] = true; // 登记：这个点来过了
- for (int k = 0; k < deg[u]; k += 1) dfs(adj[u][k]); // 再把每个邻居都走一遍
- }
- // 数连通块：for (int i = 0; i < n; i += 1) if (!visited[i]) { dfs(i); pieces += 1; }
if (visited[u]) return; // 来过就返回：这一行才是 visited 数组存在的理由
任务 3：确定 DFS/BFS 的顺序差异，并认出两个边界
建议掌握：DFS 沿一条路径尽量走到底再回头（用递归或栈），BFS 按“一层一层”向外扩展（用队列），得到的是离起点的最短步数层级；这两种顺序本质不同，不能混为一谈。拓展：BFS 的层数可以当作“最短步数”的初步认识，现在只用认识这个概念。
必会 / 建议掌握 / 拓展：必会是画出邻接关系、写访问标记、说明 DFS 与 BFS 的顺序差异。建议掌握是理解两种顺序为什么不同。BFS 层数当最短步数是拓展，现在不用当硬门槛。
- // 顺序：DFS 沿一条路径走到底再回头；BFS 按队列一层一层向外扩展
- // 边界 1：从 0 出发的 DFS 只能访问到 {0,1,2}，图里还有未访问的 3、4
- // 边界 2：遍历所有点，若某点还没访问过，就再发起一次 DFS，连通块数加一
- // BFS 层数当作最短步数（拓展）
先选出 DFS 和 BFS 顺序上的本质差异：
再选出怎么把 2 个连通块都数到：
任务 4：随机小测，看看你是否真的懂了
每次从本课题库抽出三道不同的选择题。题目与解析已通过校验，答完后看解析，不要只看分数；拿不准就回到对应任务再看一遍。