耳分解
定义
耳
对于图 $ G = (V, E) $ 和子图 $ G' = (V', E') $，耳是一个顶点序列 $ x_1, x_2, \dots, x_k $，满足以下条件：
- 任意相邻两点之间有边连接，即 $ (x_i, x_{i+1}) \in E $ 对于所有 $ 1 \leq i < k $。
- $ x_1 $ 和 $ x_k $ 都属于子图 $ V' $，即 $ x_1, x_k \in V' $。
- $ x_2, \dots, x_{k-1} $ 属于图 $ V \setminus V' $，即耳的中间部分的顶点不在子图 $ G' $ 中。
- $ x_2, \dots, x_{k-1} $ 中的顶点必须互不相同。
特别地，如果耳的起点和终点不相同（即 $ x_1 \neq x_k $），则称这个耳为开耳。
耳分解
耳分解是将图 $ G = (V, E) $ 分解成一个子图序列 $ (G_0, G_1, \dots, G_t) $，满足以下条件：
- 初始子图 $ G_0 $ 是一个环。
- 最终子图 $ G_t = G $，即分解最终得到原始图。
- 对于每个 $ i < t $，子图 $ G_i \subset G_{i+1} $，即每个子图是前一个子图的扩展。
- 对于每个 $ i < t $，差集 $ G_{i+1} \setminus G_i $ 必须是一个耳（去掉首尾顶点后的部分）。
特别地，如果所有耳都是开耳（即所有耳的起点和终点不同），则称这个分解为开耳分解。
性质
-
边双连通 \(\iff\) 该无向图存在耳分解
-
点双连通 \(\iff\) 该无向图存在开耳分解
-
强连通 \(\iff\) 该有向图存在耳分解
一个有意思的结论
设 \(G = (V, E)\) 是一个有向图，设 \(U(G)\) 为将 \(G\) 的所有有向边视为无向边后得到的无向图。若有向图 \(G\) 是强连通的，且无向图 \(U(G)\) 是点双连通的（且 \(|V| \ge 3\)），则 \(G\) 具有开耳分解。
证明：https://arxiv.org/pdf/0904.1920
How
题
P5776 [SNOI2013] Quare
给你一张有重边、无自环的无向正权图，求出它边权和最小的边双连通生成子图的边权和。
考虑把耳分解的过程反过来，每次往图中添加一个耳。每次添加一个耳复杂度是 \(O(3^n)\)，考虑一个点一个点添加，设 \(f_{S,i,j}\) 表示考虑到当前这个耳伸出来的点是 \(i\)，最终要接到 \(j\) 上。记录 \(j\) 的原因是，你要区分当前耳和之前确定的耳，因为你最终只能连到之前确定好的耳上面。
双极定向
定义
给出一张无向图和 \(s,t\)，要求给每条边定向使得定向后的图为 DAG 且入度为 0 的点仅有 \(s\)，出度为 \(0\) 的点仅有 \(t\)。
性质
给定 \(s,t\) 可以双极定向当且仅当图加上边 \((s,t)\) 之后是一个点双。
一个图的点双排成一条链就可以双极定向。可以考虑圆方树直径。
How
题
CF1916F Group Division
给你一个点双连通图，让你分成两个连通块分别有 \(n_1,n_2\) 个点。
原图是点双连通的，必然可以双极定向。
根据 DAG 的性质，拓扑序任意前后缀都是连通的。双极定向后拓扑排序取前 \(n_1\) 个点即可。复杂度线性。
qoj11115 怪诞组队法
首先特判一下图不连通的平凡情况。如果图连通，划分成两个连通块，一定会从一个点双连通分量划分开来。考虑每一个点双，点双中点的权值变成删去这个点双后这个点所在连通块大小模 3 的值，如果存在一个点权值是 2，把这个点拿出来就是合法的。否则所有点点权都是 0/1。如果只有一个 1 没法分出 2 的，否则由于模 3 余 1，至少有 4 个 1，那只要分出 2 个就行了。因为考虑的是点双，可以直接双极定向，必然存在前缀有 2 个 1。算每个点点权可以在圆方树上算子树内圆点个数，特殊考虑方点上面圆点即可。