Kameda's Algorithm / 平面 DAG 上的可达性

Kameda's Algorithm 用于解决平面 DAG 上的可达性问题。

该平面 DAG 需要满足：所有 0 入度点和所有 0 出度点在平面图的同一个面上，通常它们应该都在无界面上，并且存在一种分割该面的方式，使得所有 0 入度点属于一个部分，而所有 0 出度点属于另一个部分。

在算法的最开始，我们在图上创建一个超级源点 $s$ 和一个超级汇点 $t$，并将 $s$ 向所有 0 入度点连边，将所有 0 出度点向 $t$ 连边。由于该平面图满足之前提到的性质，在这步操作中，我们一定能维持图的平面性。

接下来，从 $s$ 开始 DFS，按顺时针方向访问每个点的出边，并记录出栈序（这里与算法原本的描述恰好相反）。然后再做一遍相同的 DFS，只不过这一次按逆时针方向访问每个点的出边，同样记录下出栈序。

这样，每个点都拥有了两个编号 $(a_u, b_u)$。我们断言，在这张平面 DAG 上，$u$ 可以到达 $v$ 当且仅当 $a_u\ge a_v$ 且 $b_u \ge b_v$。这一条件的必要性显然，我们考虑充分性的逆否命题，也即若 $u,v$ 间没有可达关系，则 $a_u<a_v$ 或 $b_u<b_v$，由于我们在两次 DFS 中采用了相反的访问出边的顺序，$u,v$ 在两次 DFS 中必然拥有不同的访问顺序。这样就简要的提供了证明。

这样我们就可以在 $O(n\log n)$ 或 $O(n)$ 的时间复杂度内，取决于你是否需要对点的出边进行排序，将平面 DAG 上的可达性问题转化为二维偏序，从而 $O(1)$ 回答查询，或者解决更加复杂的问题。

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。