可达性询问 2 题解

思路推导

把原图中的每条边反向。原问题中“顶点 $v$ 能到达某个黑色顶点”，等价于反图中“某个黑色顶点能到达 $v$”。因此，可以维护一个布尔标记，表示各顶点当前是否能在反图中由某个黑色顶点到达。

当一个顶点被染黑时，从它出发在反图上进行搜索。只有尚未被标记的顶点才会进入队列；一个已经被标记的顶点能够到达的所有顶点，必然已在此前的某次搜索中被处理过，所以不需要再次展开。

做法

建出反图。维护数组 vis 和一个队列。

处理 1 v 时，若 $v$ 尚未被标记，就标记它并入队；不断取出队首顶点，将其所有尚未被标记的反图邻点标记并入队。

处理 2 v 时，只需根据 vis[v] 输出 Yes 或 No。

正确性证明

对已经处理的操作数进行归纳。初始没有黑色顶点，所有标记均为假，与题意一致。

若当前操作是询问，算法直接报告标记值。根据归纳假设，标记为真当且仅当反图中存在某个黑色顶点到该顶点的路径，这又等价于原图中该顶点能到达某个黑色顶点，因此答案正确。

若当前操作把 $v$ 染黑，搜索会标记反图中所有能由 $v$ 到达、且此前尚未标记的顶点。此前已标记的顶点及其可达范围已经完整处理，无需再次展开。操作结束后，被标记的顶点恰好是能由任意黑色顶点在反图中到达的顶点。归纳成立。

因此，算法对所有询问均给出正确答案。

复杂度分析

每个顶点至多入队一次，每条边至多在其起点首次入队时扫描一次。总时间复杂度为 $O(N+M+Q)$，空间复杂度为 $O(N+M)$。