耳分解与双极定向

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132112802

耳分解

对于无向图中的任意边双和有向图中的任意强联通都可以按照此方法构造：

1. $S=\{u\}$

2. 每次找 $S$ 的两个元素 $u,v$ （可相同），找一条 不经过 $S$ 的路径 ，并把路劲上的所有点加入 $S$

可以拿来dp，来构造某种条件的边双。

常用的状态设计 $f(S)$ ，然后枚举 $T$ 为 $S$ 补集的子集。再枚举 $u,v\in S$ 。这种是 $O(3^n\times n^2)$ 。

部分题目可以： $f(S,i,j)$ 当前在 $i$ 目标点为 $j$ ，然后转移可以枚举 $j$ 或者是不在 $S$ 中的点。 $O(2^nn^2)$

• [SNOI 2013] Quare 无向图的

• Gym 102759 C 有向图

双极定向

给无向图每条边定向后可以变成DAG，且 $s$ 为总起点， $t$ 为总终点。

一般会在圆方树上乱搞。过段时间要去整理一下。

• Codechef CUREK

• [洛谷月赛] 白鹭兰

双极定向有个优良性质：考虑其拓扑序为 $p$

则 $p_s,\dots,p_i$ 和 $p_{i+1},\dots p_t$ 的子图都联通。