耳分解和双极定向的瞎写。

· · 个人记录

本文是瞎写，我是民科，不对正确性负责。。。

大概对一个点双双极定向，s\to t。

大概就是从 s 开始dfs，建出dfs树，进行耳分解。

首先耳分解就是给你了一个点双，让你去吧这一个点双切成若干个耳朵。

我们需要的是把这个图的边集进行一个有序划分，每一个边集是一个在除了首尾都简单的路径（可以首尾相同，但是除首尾外点不可以重复）（也就是一条链或者一个简单环）（称作耳朵）。

使每次只有加入的边集的首尾节点是原先点集中存在的，当然第一个不算。

这个不合法。

由于我是民科，我不管证明，只写一下如何求。

如何对一个点双进行耳分解？

  1. 建出dfs树，由于是无向连通图，所以除了树边只存在返祖边

对于每个点都有 x\to y,那么 \text{low}_y<\text{dfn}_x。

然后呢？

减量法？就是倒着的增量法。

考虑每次把一个（一些）耳朵切掉，使得剩下的是一个点双。

我们只能允许一个耳朵 不在首位地 包含一个点 x 。就是被插入的那个耳朵。

那么我们钦定对于所有 x\to y 的 y 我们只从 \text{low}_y 最小的选。（类似DP转移点？）

剩下的我们就切掉。

这个构造是为了满足仍是点双。

考虑其实我们每次走的只有 \mathrm{argmin(low(y))} 所以可以做到 O(m)

双极定向。

我们只需要对每一个耳朵定向。

一个耳朵里的方向只有两种，除了最后一个返祖边，剩下的必须全是一个方向。

可以发现我们对于 x\to y 的 y 反的祖一定要比 x 反的祖要深。

而相互交错可以保证无环。（考虑如果不交错有可能产生环）。

但这只是dag定了单极，并不是双极。

考虑我们是在把每一个耳朵尽可能把他的low最小化，所以为了终点在 s，我们不妨把 \text{dfn}_s 设为 -1。