题解：社交网络动态合并与传递关注

问题分析

本题需要维护一个有向图（关注关系），并支持动态添加有向边，同时在每次添加后立即进行一个“活动”——按照特定规则不断添加新的有向边，直到无法继续。我们需要在每次添加边后，输出图中所有顶点的出度和（即每个用户关注人数的总和）。

核心规则是：如果存在三元组 $(x,y,z)$，使得：

• $x$ 关注 $y$
• $y$ 和 $z$ 互相关注
• $x$ 未关注 $z$

那么可以添加边 $x \to z$。这个过程可以反复进行，直到无法找到这样的三元组。

核心观察

1. 强连通分量性质
   互相关注关系具有传递性：如果 $a$ 和 $b$ 互相关注，$b$ 和 $c$ 互相关注，那么通过规则可以推导出 $a$ 和 $c$ 之间也会建立互相关注关系。这意味着，在一个强连通分量（SCC）内，所有顶点最终都会两两互相关注。

2. 分量间的边
   考虑两个强连通分量 $C_1$ 和 $C_2$。如果存在一条从 $C_1$ 中某个顶点到 $C_2$ 中某个顶点的边，那么 $C_1$ 中的所有顶点最终都会关注 $C_2$ 中的所有顶点。因为：

   • 取 $x \in C_1, y \in C_1$（$y$ 被 $x$ 关注）
   • 取 $z \in C_2$，由于 $y$ 和 $z$ 互相关注（在同一SCC内）
   • 则可以添加 $x \to z$

   进一步，如果存在 $C_1 \to C_2$ 和 $C_2 \to C_1$ 的边，那么两个分量实际上会合并成一个更大的强连通分量。

3. 数据结构设计
   我们可以维护强连通分量的集合，以及分量之间的有向边。对于每个分量 $C$：

   • sz[C]：分量大小
   • in[C]：有哪些顶点（来自其他分量）关注了 $C$ 中的顶点
   • out[C]：$C$ 中的顶点关注了哪些其他分量，以及通过哪个顶点关注的

算法流程

初始化

• 每个顶点初始是一个独立的分量
• ans 初始为 0

添加边 $(a,b)$

1. 找到 $a$ 和 $b$ 所在的分量 fa 和 fb
2. 如果 fa == fb 或 $a$ 已经在 in[fb] 中（即 $a$ 已经关注了 $fb$ 中的某个顶点），直接返回
3. 检查是否已存在从 fb 到 fa 的边：
   • 如果不存在：添加边 fa → fb，更新数据结构，ans 增加 sz[fb]
   • 如果存在：说明 fa 和 fb 之间形成了双向边，需要合并两个分量

合并分量

1. 将较小的分量合并到较大的分量中（启发式合并）
2. 合并时：
   • 处理原小分量的所有入边：删除这些边，更新 ans
   • 处理原小分量的所有出边：删除这些边，更新 ans
   • 合并两个分量的顶点集合
   • 重新添加被删除的边（但指向新的合并后分量）
3. 合并后，新分量的入边和出边可能需要进一步触发合并（递归处理）

正确性证明

1. 强连通分量维护
   算法保证了当两个分量之间有双向边时立即合并，这等价于维护了图的强连通分量。

2. 边的传播
   当一个分量 $C_1$ 有边指向 $C_2$ 时，$C_1$ 中所有顶点最终都会关注 $C_2$ 中所有顶点。我们的数据结构记录了这种"分量间关注"关系。

3. 答案计算
   总关注数 ans 维护为：

   • 每个分量内部的互相关注数：sz[C]*(sz[C]-1)
   • 分量之间的关注数：对于每个从 $C_1$ 到 $C_2$ 的边，贡献为 sz[C1] * sz[C2]

   合并时正确更新这些贡献。

复杂度分析

• 时间复杂度：使用启发式合并，每个顶点最多被合并 $O(\log n)$ 次。每条边最多被处理 $O(\log n)$ 次。总复杂度 $O(m \log n)$。
• 空间复杂度：$O(n + m)$。

总结

本题是一道巧妙的数据结构题目，主要考察：

1. 图论转化能力：将复杂的传递规则转化为强连通分量的合并问题。
2. 并查集应用：使用并查集维护强连通分量。
3. 启发式合并：通过将小集合合并到大集合中来保证复杂度。
4. 集合维护技巧：使用 set 维护分量的入边和出边。

算法的核心在于认识到：活动规则本质上是在不断地合并强连通分量，并维护分量之间的完全二分关注关系。通过精心设计的数据结构，我们可以在 $O(m \log n)$ 时间内处理所有操作，满足题目的大数据范围要求。