好友加删日志最早全连通：先给正确重算，再讨论离线优化

题目重点：删除不能用普通并查集拆开组件，直径限制也不是连通性。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

初始n个孤立用户，日志按时间排序；同时间依输入顺序应用全部事件后检查，返回最早满足时间。
add重复幂等、remove不存在边幂等；可选diameter_limit要求每对最短距离≤K。n=1且无日志时初始成立时间未定义，返回None并需调用方另给初始时刻。

解题路线

维护邻接set，每个时间组更新后BFS检查从0是否到全部用户。该基线支持删除且语义简单可独立验证。
仅加边时可用DSU维护componentCount，降到O(Mα(V))；加入任意删除后标准DSU不再足够。已知完整日志可把边活跃区间放segment tree时间轴，用rollbackDSU回答连通，不能用路径压缩而不记录全部变更。
直径≤K需要距离信息，DSU只知道同组件。基线全点BFS取最长最短距离；在一般图中只做两次BFS不保证得到准确直径。

手动走一遍

t1加0−1，t2加1−2→全连通最早2；若同t2又删0−1且按组末检查，则t2不满足。路径0−1−2−3连通但直径3；K2失败，新增0−3形成4环后直径2满足。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from itertools import groupby
from collections import deque


def first_connected(n,events,diameter_limit=None):
    if n<=0 or diameter_limit is not None and diameter_limit<0:
        raise ValueError("positive n and nonnegative diameter required")
    graph=[set() for _ in range(n)]
    for time,group in groupby(sorted(events,key=lambda e:e[0]),key=lambda e:e[0]):
        for _,op,u,v in group:
            if not 0<=u<n or not 0<=v<n or op not in ('add','remove'):
                raise ValueError("invalid event")
            if op=='add':graph[u].add(v);graph[v].add(u)
            else:graph[u].discard(v);graph[v].discard(u)
        def distances(start):
            d={start:0};q=deque([start])
            while q:
                u=q.popleft()
                for v in graph[u]:
                    if v not in d:d[v]=d[u]+1;q.append(v)
            return d
        d=distances(0)
        if len(d)==n and (diameter_limit is None or all(max(distances(u).values())<=diameter_limit for u in range(n))):
            return time
    return None

复杂度

连通重算O(T(V+E))，T为不同事件时刻；加直径检查O(TV(V+E))最坏。离线rollback提升连通查询但不能声称同时O(logM)求任意动态图直径。

易错点与追问

容易失分的边界

取“此后永远连通”的时间与“首次连通”不同，删除使性质不单调。
同一时间中间状态是否算成立必须确认，本文只检查整组完成。

继续深挖

返回最后一次不连通后的永久成立时间，离线扫描如何改？
边多次重复add/remove时如何记录活跃计数/区间而不产生假删除？