题目重点：按时间处理 rider A 与 B 的同乘关系，用并查集在连通分量归一时返回最早时间；block 追问涉及删边，题目语义未给，单独说明。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 给定完整 rider 集合以及 (timestamp,A,B) 日志；同乘关系按无向边加入，之后持续有效，重复同乘无新影响。题目未说明 rider 集合如何给定，本文把它作为显式输入，避免只从日志推断而漏掉未出现的人。
- 时间戳可相同，答案为第一个使所有已知 rider 同属一个连通分量的时间值；0 或 1 个 rider 训练约定返回 0，从未全连通返回 None。
- 主代码只处理加边。block 如果移除边或禁止未来边，会改变连通性单调性，具体语义要先核对，不能在主代码里私自定义。
解题路线
- 按 timestamp 升序遍历日志，开始时每个 rider 是单独分量，维护 components=人数。每条 (A,B) 查各自根，若不同则按大小合并并将 components 减一；首次降到 1 就返回该日志时间。
- 连通性在只加边模型下只会从假变真，不会回退，因此第一次 components=1 的时间就是最早答案；重复边或同一 rider 自环不改变 components。
- 路径压缩与按大小合并让每条 union/find 摊还接近常数。若日志已按时间排序可直接 O(L·α(R)) 扫描；乱序需先 O(L log L) 排序。
- block 追问必须先问：是永久删掉两人已有同乘边、只禁止未来连接，还是有向的社交屏蔽？若已有边能被移除，DSU 无法拆分，少量事件可每次从当前边集 BFS/DFS；大量离线增删可讨论时间线段树加 rollback DSU，前提是确切的无向边生效区间。
手动走一遍
riders=[A,B,C,D]，日志 t=2 A-B、t=3 C-D、t=5 B-C。前两条后有两个分量，t=5 合并后首次只剩一个，返回 5。若 D 从未出现在日志中，不能仅按出现过的 A/B/C 算出‘所有’连通；必须明确全集。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Earliest timestamp at which all known riders become connected."""
def earliest_connected(riders: list[str], logs: list[tuple[int, str, str]]) -> int | None:
if len(set(riders)) != len(riders):
raise ValueError("rider IDs must be unique")
if len(riders) <= 1:
return 0
index = {rider: i for i, rider in enumerate(riders)}
parent = list(range(len(riders)))
size = [1] * len(riders)
components = len(riders)
def find(i: int) -> int:
while parent[i] != i:
parent[i] = parent[parent[i]]
i = parent[i]
return i
for timestamp, left, right in sorted(logs, key=lambda item: item[0]):
if left not in index or right not in index:
raise ValueError("log contains unknown rider")
a, b = find(index[left]), find(index[right])
if a != b:
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
components -= 1
if components == 1:
return timestamp
return None
复杂度
R 个 rider、L 条日志：排序 O(L log L)，DSU 扫描 O(L·α(R)) 摊还，父节点/大小表 O(R)。若每次 block 后都重新 BFS，单次 O(R+E)，不应再声称 DSU 更新为 O(α(R))。
易错点与追问
容易失分的边界
- 只从日志提取 rider ID 当全集，静默排除从未同乘的 rider，使最早全连通时间虚假提前。
- 把同乘关系当有向边，误用强连通；题目的‘互相 connected’按训练约定是无向可达。
- 遇到 block 事件还沿用只支持合并的 DSU；删边可能把一个分量拆成多个。
- 相同时间戳的日志在处理到某一条时返回该时间仍正确，但若输出还要求当时完整图，应处理完该时间批次再生成快照。
继续深挖
- 如果 block 只阻止未来 rider 关系而不删除既有边，主 DSU 是否仍可用？要在哪一步拒绝新边？
- 如果 block 是有向且只改变‘可以互相看到’而非乘车连通，为什么图模型需要重新定义？
- 若要求查询每个时刻的分量数且有边的增删，如何构造离线活动区间并使用 rollback DSU？
