首先考虑没有退群操作该如何做。 如果把每名学生看做一个点，把同一个群里的所有人都用无向边连接，那么题目就是求 111 号学生所在连通块的大小。这显然是并查集的经典应用。于是我们给每个群的学生连接起来求并查集的大小即可。注意并不需要每两个学生都连接一次，会超时。我们可以选择每个群第一个学生为父节点，其他学生全部向父节点连边。 加入删边（即退群）操作后，并查集显然无法做到删边的功能（期待有神犇能搞个可持久化并查集来打脸我bushi）。但是如果我们离线处理询问，将删边操作倒过来，不就是加边了？于是我们将删边操作倒序枚举，每遇到一次删边就反过来加边，同时将答案存起来倒序输出，就可以使用并查集做到了。 注意细节：由于倒序后一开始处理的情况是所有能退群的学生都退群后的，所以我们加边时需要检查：如果当前群里枚举到的这个学生在退群操作中出现过，那么不能把他加入群里。这样有可能第一个学生不能在一开始就被加入群中，因此每个群的父节点应改为第一个加入群的学生。

暴力是很显然的。直接去掉边再跑搜索。 发现操作只有删除，想到逆序操作就变成了增加。 很显然的并查集，在上面多维护一个集合大小就好了。 注意维护一下合并的顺序，无关删除的直接合并，有关的按照输入的逆序处理，最后答案倒过来输出。 别忘了并查集维护的是集合大小，所以用 nnn 减去集合大小才是答案。 此时还并没有做完。 容易发现，暴力枚举每一个群内的两人关系再合并的时间复杂度过大，所以我们创建 mmm 个虚点编号为 n+1n+1n+1 到 n+mn+mn+m 表示群聊。 这样我们的复杂度就很低了。 注意，虚点的集合父亲为本身，大小初始化为 000。这是因为我们只关心人，而不关心群聊。 时间复杂度：O(qlog⁡(n+m))O(q \log (n+m))O(qlog(n+m)) Code:

并查集 在解决当前问题时，正向处理存在较大难度，往往需要多次断边，才能成功去除某一连通块。既然直接删边操作复杂，不妨尝试采用离线算法来简化计算。 我们可以逆向思考，将删边操作转换为加边操作。从最后一次删边开始倒序处理，这样问题就转化为：给定一个图，逐步向图中添加边，并在每次加边后确定班长能够通知到的学生集合。我们可以通过并查集解决这个问题。 时间复杂度 O(n)