双极定向

· · 算法·理论

无向图 G 的双极定向指的是,将 G 定向为 DAG,满足 S 是唯一零入度点,T 是唯一零出度点。

双极定向存在的充要条件是,原图的广义圆方树是 S \to T 的毛毛虫。

构造双极定向模板:CF730K Roads Orientation Problem。

我们求出以 S 为根的 DFS 树,将 S \to T 的路径定向为 \downarrow 。

维护队列 Q,初始令 (T,\downarrow ) 入队。每轮操作中取出点 u 和方向,然后在 DFS 树上跳祖先定为同向,直到碰到已标记边结束。均摊下来是线性的。

需要处理返祖边。对 (x,y) 定向时,若碰到返祖边 (x,z),且 z 在 y 子树中,则需要定向 x \to z,对 z \to y 定反方向。实现时将 (z,\uparrow) 入队即可。复杂度线性。