题解：AT_abc420_e [ABC420E] Reachability Query

simple_child · 2025-08-25 14:44:50 · 题解

给定一个包含 N(1 \leq N \leq 2 \times 10^5) 个顶点、0 条边的无向图。顶点编号为 1,2,\dots,N，初始时所有顶点均为白色。
请处理总计 Q(1 \leq Q \leq 6 \times 10^5) 个以下 3 种类型的查询：

1. 添加一条连接顶点 u 和 v 的无向边。(1 \leq u < v \leq N)，在该查询之前，未添加过连接 u 和 v 的边。
2. 将顶点 v( 1 \leq v \leq N ) 的颜色反转。
3. 判断从顶点 v( 1 \leq v \leq N ) 出发，经过 0 条或多条边后能否到达某个黑色顶点。若能到达，输出 Yes；若不能到达，输出 No。

不是特别裸的并查集。也是挂了一发。
先分析一下。首先操作 1 就是合并两个以 u,v 为顶点的集合；操作 2 其实是找到顶点 v 所在连通分量的根节点，反转 v 的颜色时同步更新连通分量的黑色顶点数量和该分量是否有黑色顶点；操作 3 本质上是检查顶点 v 所在连通分量是否存在黑色顶点。

知道这些之后这题就很裸了，直接套个模板就完事了。
C++通过代码。
这里的代码用了按秩合并和路径压缩，整体时间复杂度为 O(Q\times α(N))。如果不太会并查集的可移步 我的随笔。