微博转发问题题解
题目概述
给定一个有向图，表示用户之间的“关注”关系。若 A 关注 B（即存在有向边 A → B），则 A 是 B 的粉丝。当编号为 ID 的用户（小末）发布微博时，所有能直接或间接关注到小末的用户都会转发该微博。求转发的总人数（不包含小末自己）。
问题分析
关键转化
* 原问题：求有多少个节点 X，在原图中存在路径 X → … → ID。
* 等价问题：在反向图中，从 ID 出发能到达多少个节点（不含 ID 自身）。
> 为什么用反向图？
> 在原图中对每个节点判断是否能到达 ID，需要对每个点做搜索，复杂度极高。而将所有边反向后，“X 能到达 ID” 等价于 “在反向图中 ID 能到达 X”，只需从 ID 开始做一次 BFS/DFS 即可求解。
建图规则
输入 含义 反向图操作 A B A 关注 B（A→B） rev[B].push_back(A)
示例验证
以样例 1 为例，ID=1。构建反向图后从节点 1 开始 BFS，可访问到的新节点集合为 {2, 3, 4, 5, 6}，共 5 个，因此输出 5 ✅。
算法设计
1. 读取测试数据组数 T。
2. 对每组数据：
* 读取 N（关系数/边数）和 ID（小末编号）。
* 构建反向邻接表 revGraph。
* 从 ID 开始 BFS，统计新访问的节点数 count。
3. 按格式输出 Case #x: count。
复杂度分析
指标 复杂度 说明 时间 O(N + V) V 为实际出现的节点数，每条边和每个节点最多被访问一次 空间 O(N + V) 存储反向邻接表和访问标记数组
N ≤ 10⁵，该复杂度完全可接受。
C++ 代码实现
