题目重点：兄弟姐妹可能互不可达，却共享祖先，所以不是查一条路径。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- parents映射子→父母，已经验证为无环亲缘DAG；可多父母，不凭树结构假设只有一个parent。
- 训练定义两者祖先集合包含本人，存在共同祖先即related；收养/族群/遗传程度不是此计算合同。
解题路线
- 分别沿父指针搜索全部祖先，用seen防重复公共分支。取两集合交集非空即可。
- 包含本人使一方是另一方祖先也成立；若题目要求仅共同严格祖先，移除自己会改变父子等情况，必须先明确。
- 多查询可预存祖先bitset或memo，数据更新会失效；新增关系前需检测是否引入环，不能用seen消掉循环就称合法谱系。
手动走一遍
A/B都以P为父，A到B没有父边路径，但两祖先集合含P，因此True。只有A→P、B→Q且无其他共同祖先则False；同一人按本文定义True。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def related(parents,a,b):
# parents maps a child to zero or more direct parents; DAG validity is a precondition.
def ancestors(person):
seen={person};todo=[person]
for u in todo:
for v in parents.get(u,()):
if v not in seen:seen.add(v);todo.append(v)
return seen
return bool(ancestors(a)&ancestors(b))
复杂度
单query O(V+E)最坏时间、O(V)工作空间；预存全部祖先可O(V²)位存储，稀疏DAG也可能祖先密集。
易错点与追问
容易失分的边界
- 无向DSU同家谱组件比共同祖先更宽，例如通过配偶连接不能据此断定共同祖先。
- 数据本身真假/遗传定义需外部证据，图算法只计算给定关系。
继续深挖
- 需要最近共同祖先，DAG可能多个不可比较候选，如何定义最近？
- 返回一条双方到共同祖先的证据路径，搜索要保存什么？
