前言
若有长风绕旗，那便是我在想你了。
这周讲了个图论连通性板块的一些进阶知识，周六全国第一给我们讲了一些树上的问题，感觉树剖板块实现难度较大，后面几道偏思维的题会有些许好转。
这里就先写写连通性相关的进阶的一些知识点吧。
主要涵盖：耳分解，双极定向，三连通分量和一些重要的结论。
（其实我不会告诉你大部分都是我抄的 \(\text{2023}\) 年的集训队论文。）
建议先理解透彻双连通分量以及圆方树的相关知识和求法再来进阶，不然就会像我一样，调半天的三连通分量，因为下面这张图：
耳分解
\(\large \mathbf{Difinition \ 1}\)
我们有如下对于耳，开耳的定义：
在无向图 \(G=(V,E)\) 中，有一个子图 \(G'=(V',E')\)，若存在简单路径或者简单环 \(P:x_1\to x_2\to x_3.....\to x_t\)，满足 \(x_1,x_t\in V',\forall i\in [2,t-1],x_i\not\in V'\)，则称 \(P\) 是 \(G\) 中关于 \(G'\) 的耳，如果 \(P\) 是简单路径，那么则称 \(P\) 是 \(G\) 关于 \(G'\) 的开耳。
\(\large \mathbf{Difinition\ 2}\)
我们再给耳分解下一个定义。
对于无向连通图 \(G=(V,E)\)，有一个连通子图序列 \((G_0,G_1,....G_k)\)，满足以下条件：
- \(G_0\) 是一个简单环（一个点也是可以的），以及 \(G_k=G\)。
- \(\forall i\in [1,k]\)，\(G_{i-1}\) 是 \(G_i\) 的子图。
- 如 \(G_i=(V_i,E_i)\)，那么 \(E_i \setminus E_{i-1}\) 就是 \(G\) 中关于 \(G_{i-1}\) 的耳。
满足上述条件的连通子图序列，就称为 \(G\) 的一个耳分解。
当然，这里的耳分解将里面所有的耳换成开耳就可以得到开耳分解的定义。
\(\large \mathbf{Theory\ 1}\)
无向连通图 \(G=(V,E)\) 中存在耳分解当且仅当图 \(G\) 边双连通。
相当于两者之间是个充要条件的关系，故我们分步证明。
先证必要性，即 \(G\) 存在耳分解 \(\to\) \(G\) 边双连通:
- 假设 \(G\) 的耳分解是 \((G_0,G_1,....,G_k)\)。根据定义，\(G_0\) 显然边双连通，而在 \(G_i\) 边双连通时，对于 \(G_{i+1}\) 的加入，可以发现 \(E_{i+1}\) 内部显然不可能存在一条割边（因为你总是能从两个方向中的一个到达这个点），故 \(G_{i+1}\) 也满足边双连通，然后根据数学归纳法，\(G\) 边双连通。
再证充分性，即 \(G\) 边双连通 \(\to\) \(G\) 存在耳分解：
- 首先，如果 \(|E|=0\)，那么显然 \(|V|=1\)，显然成立。
- 否则，先以一为根，搞出图 \(G\) 的一颗搜索树，然后按照如下方式构造耳分解：
- 第一步，由于这个图是边双联通的，故我们一定可以找到一条非树边 \(1\to x\)，那么这条边就会和 \(1\sim x\) 这条路径构成一个简单环，我们钦定这个简单环就是我们要构造的 \(G_0\)。
- 第二步，假设现在已经生成了连通子图的序列 \(G_i\)，如果 \(G_i\) 的点集 \(V_i\not= V\)，找到一个点 \(x\) 满足 \(x\notin V_i \ \wedge\) \(x\) 在搜索树上的父亲 \(y\in V_i\)。仍然通过边双连通的性质，我们一定可以找到一条路径 \((u,v)\) 满足 \(u\) 是 \(y\) 的祖先，\(v\) 是 \(x\) 的后代，可以发现，\(v\to u\) 这条边和 \(y\sim v\) 这条路径，就会构成一个新的耳，且至少含有一个新点 \(x\)，令 \(G_{i+1}\) 表示 \(G_i\) 加上这个耳。（可以发现，由于 \(G_i\) 一直是一个包含了根节点的联通块，所以在 \(V_i\not= V\) 时，这样的 \(x\) 显然是一直存在的。
- 第三步，我们在 \(V_i\not= V\) 的时候持续进行第二步，必然只会在最后 \(V_i=V\) 时终止。可能这个时候边集还 \(\not= E_i\)，可以发现未加入的每条边和他的两个端点会分别构成一些耳，然后依次往 \(V_i\) 里面放入即可。
于是证毕。
\(\large \mathbf{Theory\ 2}\)
标签：知识点,连通,连通性,进阶,子图,开耳,分解,边双 From： https://www.cnblogs.com/SFsaltyfish/p/18637540至少含有三个点的无自环无向连通图 \(G\) 存在开耳分解当且仅当 \(G\) 点双连通。