OlveraeUNSW
返回题目列表
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