题目重点：Phone Coding 题目给 root 与 sendAsyncMessage/receiveMessage，先数节点，再返回结构并处理消息失败重试；本文明确消息身份与终止条件。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版 cluster 是无向图，root 可达部分就是要统计的 cluster；每节点有稳定唯一 ID，查询该节点可得到邻居 ID 列表。
- 代码把给定 send/receive 封装成异步 query(node,requestId)；调用方需为每次请求设置超时，丢回复时抛 TimeoutError。相同 requestId 的重复响应要在适配层合并或忽略。
- 邻居回复可能包含重复 ID，节点可形成环；最多重试 3 次，耗尽后向上报告失败，不把部分结果当完整计数。并发上限训练设 16。
解题路线
- 从 root 建 seen ID 集合与 BFS frontier；同一层节点并发查询邻居，但由 semaphore 限制同时在途请求数。
- 每节点固定 requestId，超时后用同一 ID 重试；处理回复时先对邻居去重，再按 seen 判断是否首次发现，只有首次发现才加入下一层。
- 返回结构保存 node→排序后的直接邻居列表；节点数等于 seen 大小。若传输重复投递了整个回复，也只能处理同一请求 ID 一次。
- 一层查询全部完成后才处理并生成下一层；frontier 空且无未完成请求时终止，避免因为消息暂未到达而过早宣布完成。
- 若大量节点/高直径不宜层同步，可改为 work queue + pending-in-flight 计数；每次发现新 ID 只入队一次，队列空且 pending 为零才可终止。
- 随机生成 1,000 张含环的图，模拟首轮超时与重复邻居，与独立 deque BFS 的可达集和邻接表对照。
手动走一遍
A 邻接 B,C，B 邻接 A,C，C 邻接 A,B。A 回复把 B 重复给两次，seen 仍只把 B 入队一次；B 首次请求超时后同 requestId 重试。三节点的结构都收集完，返回 count=3。若 B 三次都失败，必须报错而不是返回 2。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Training adapter: query(node, request_id) asynchronously returns neighbor IDs."""
import asyncio
from collections.abc import Awaitable, Callable
async def discover_cluster(
root: str,
query: Callable[[str, str], Awaitable[list[str]]],
max_concurrent: int = 16,
max_attempts: int = 3,
) -> tuple[int, dict[str, list[str]]]:
if max_concurrent < 1 or max_attempts < 1:
raise ValueError("concurrency and attempts must be positive")
semaphore = asyncio.Semaphore(max_concurrent)
seen = {root}
frontier = [root]
structure: dict[str, list[str]] = {}
async def fetch(node: str) -> list[str]:
request_id = f"discover:{node}"
for attempt in range(max_attempts):
try:
async with semaphore:
return await query(node, request_id)
except TimeoutError:
if attempt == max_attempts - 1:
raise
raise AssertionError("unreachable")
while frontier:
replies = await asyncio.gather(*(fetch(node) for node in frontier))
next_frontier = []
for node, neighbors in zip(frontier, replies):
structure[node] = sorted(set(neighbors))
for neighbor in structure[node]:
if neighbor not in seen:
seen.add(neighbor)
next_frontier.append(neighbor)
frontier = next_frontier
return len(seen), structure
复杂度
可达节点 V、无向边 E，成功邻居响应总大小 O(V+E)，本地去重与处理期望 O(V+E)；每层最多 16 个在途请求，BFS 同步轮数为图直径级，最多 R 次重试把请求上界增至 O(RV)。保存 seen、结构与邻接列表为 O(V+E) 空间。
易错点与追问
容易失分的边界
- 靠收到的消息数而非唯一节点 ID 计数，重试和重复回复造成多算。
- 没有稳定 requestId，接收端无法区分重试与新请求。
- 只等当前 receiveMessage 返回一次就宣布全图已遍历。
- 重试耗尽后静默返回不完整拓扑。
- 异步 API 直接无限并发查询，节点多时耗尽连接和内存。
继续深挖
- 节点在遍历期间加入/离开，如何定义快照或最终一致的计数？
- 若图是有向的，“cluster”是可达集还是强连通分量？
- send 成功但回复丢失时，被查询节点的副作用应如何做到幂等？
- 百万节点跨机运行时，seen 集合和工作队列怎样分片并检测全局终止？
