返回题目列表
COMP2521
BFS · 可达顶点数 numReachable
BFS · 从源点能到几个顶点(2521 21T3 真题)
读入一张有向图和一个源点 src,输出从 src 出发能到达的顶点总数(包含 src 自己)。用 BFS 或 DFS 都行。
请补全 numReachable:从 src 出发遍历,把所有访问到的顶点标记,最后数有多少个被标记。
易错点(正是错误实验室里的坑):① 一定要用visited[]标记,否则有环图会无限绕圈(死循环)。② 标记的时机要在<strong>入队/首次访问时</strong>,不是处理完才标。③ 别忘了src自己也算 1 个。
输入
- 第 1 行:
V E(顶点数、边数)。 - 接下来
E行:每行u v,表示有向边u → v。 - 最后一行:源点
src。
输出
- 一行:从
src可达的顶点数(含自身)。
示例:输入 4 2 / 0 1 / 1 2 / 0 → 输出 3(0 能到 0、1、2,到不了 3)。
样例
stdin
4 2 0 1 1 2 0
期望输出
3
stdin
5 3 0 1 0 2 3 4 0
期望输出
3
c-dcc
14