题目重点：先确认跨用户是否允许串边，再建有向图、visited与零跳合同。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 题目表含userId、初始url和目的地url，问url1能否到url2；未明确是否按用户过滤或全站汇总，这是影响答案的关键缺口。
- 本文训练接口必须给user_id，只用该用户记录，有向边source→destination，允许多跳；start==target按零跳可达。若原题是全局导航，应另建全局图，不能默认混用。
- URL以精确字符串/键比较，canonicalization、时间先后、session和当前访问权限未给。本题只判观察到的边构成的图，不承诺用户未来可执行。
解题路线
- 过滤指定用户后建邻接表，以set去重重复记录。初始URL与目标URL是方向，不建无向边；孤立目标若不是start且从邻接找不到，返回false。
- BFS从start出发，在入队时记录visited，避免环/重复路径无限入队；遇到target返回true。这里只求存在性，不需要all simple paths或最短路径数量。若要路径可记录parent后回溯。
- 跨用户串边可能制造假阳性：甲有a→b，乙有b→c，全局图可达a→c，但甲的记录并不支持。若按session/时间匹配，需要把状态扩成session或排序后的时间事件，普通静态BFS不保证时间合法。
- 观察到的跳转与权限图不同：边只说明一次历史跳转，不能证明所有用户拥有目标权限。正式要求“能否访问”若指授权检查，要查询角色/ACL与当前资源状态，题面必须确认。
- 很多查询可复用每用户索引/源点可达缓存，图版本改变需失效；全对可达矩阵O(V²)空间常不适合大URL集合。保留按需搜索基线，按查询量和更新频率选择索引。
- 独立参考按用户建立矩阵做Floyd传递闭包核全部源/目标，不复制BFS；225,000查询包括环、自环、重复边、缺失路径和多个用户。
手动走一遍
甲记录a→b,b→a，乙记录b→c。甲a→c为false；乙b→c为true。甲a→a在零跳合同下true，即使甲无a记录也仍按定义true；若题要求至少一次实际跳转，这个边界需改并明确。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
def can_reach(records, user_id, start, target):
"""Training contract: one user's observed directed URL transitions only."""
graph = {}
for uid, source, destination in records:
if uid == user_id:
graph.setdefault(source, set()).add(destination)
queue = deque([start])
seen = {start}
while queue:
node = queue.popleft()
if node == target:
return True
for nxt in graph.get(node, ()):
if nxt not in seen:
seen.add(nxt)
queue.append(nxt)
return False
复杂度
扫描全输入R建单用户图O(R)，遍历O(V+E)，空间O(V+E)；重复查询若已建索引不必每次扫R。字符串哈希与存储成本另受URL长度影响。
易错点与追问
容易失分的边界
- 未确认user过滤。
- 有向边反向也加入。
- 出队才visited导致重复膨胀。
- 把历史可达当实时授权。
- 时间受限问题仍用静态图。
继续深挖
- 必须按事件时间递增，状态怎样改变？
- URL canonicalization哪些部分不能随意删？
- 有图更新的可达缓存怎样失效？
- 返回最短见证路径怎样记录parent？
