连通块:数一数有几个朋友圈

跟打练习 难度 4

#graph-basics#dfs

从一个点出发,DFS 能走到的所有点是一个"连通块"。整张图有几个互不相连的圈子?挨个没访问过的点放一次 DFS 就数出来了!

知识点讲解

连通块计数模板:for 每个点 → 没访问过就 cnt++ 并从它 DFS(把整个圈子标记掉)。DFS 里:标记自己 → 递归所有没访问的邻居。这是 J 复赛出场率极高的模板。

改编自:GESP C++ 七级考纲 · 图的遍历|考点:DFS 连通块计数模板

来小码星球,动手写一遍 →