双连通分量

定义

关于点双和边双的定义不在过多阐述。

• 点双连通：若 \(u, v\) 处于同一点双连通分量中，则 \(u, v\) 点双连通。
• 边双连通：若 \(u, v\) 处于同一边双连通分量中，则 \(u, v\) 边双连通。

性质

研究双连通的性质时，最重要的是把定义中的基本元素 —— 割点和割边的性质理清楚。然后从整体入手，考察对应分量在原图上的分布形态，再深入单个分量，考察分量内两点之间的性质。

接下来的性质可能不会很有上下文逻辑，我尽力写了一个比较好的推导过程。

边双连通

下文中的迹为一条边不重复的路。

我们定义两点间的必经边为连接两点间所有迹的交。容易发现两点之间任意一条迹上的割边就是两点间的必经边。

将边双缩点后显然会形成一个树结构，称为边双缩点树，添加任意一条边 \((u, v)\) 则 \((u, v)\) 所在边双在缩点树上的简单路径上的所有边双会变为一个大边双。

边双连通具有传递性，即若 \(a, b\) 与 \(b, c\) 分别边双连通则 \(a, c\) 边双连通。

结论 \(1\)：\(u, v\) 边双连通当且仅当 \(u, v\) 之间没有必经边。

结论 \(2\)：对于边双内部任意一条边 \((u, v)\)，存在经过 \((u, v)\) 的回路；对于边双内部任意一点 \(u\)，存在经过 \(u\) 的回路。

原理考虑最大流最小割定理在无向图上的应用。如果 \(s \to t\) 的最大流为 \(f\) 则说明 \(s \to t\) 存在 \(f\) 条边集不交的迹，且 \(f\) 无法更大； 若最小割为 \(c\)，则存在 \(c\) 条边使得断开后 \(s, t\) 不连通，且 \(c\) 无法更小。

放到点双上，对于 \(u, v\) 至少要断开两条边才能使它们不连通，于是 \(u, v\) 之间至少存在两条边互不相交的迹。结论成立。

点双连通

类似地，我们定义必经点。请注意：两点间的割点未必就是必经点。如 \(G = \{(1, 2), (1, 3), (2, 3), (3,4)\}\)，\(3\) 是割点但不是 \(1 \to 2\) 的必经点。

对于一条边 \((u, v)\) 连接的两个点 \(u, v\) 一定点双连通。你可能会疑惑如果左边右边各有一个环，中间一条边连着，那连接的这条边的两个端点是否点双连通？事实上点双是按边来划分的，所以对于 \((u, v)\) 这条边本身就是一个点双。

根据上面的例子我们还能够说明：点双包含原图割点，但对于该点双，删去割点后该点双仍然连通。

同样根据上面的例子会发现：点双之间可能有交，因此点双连通不具有传递性。我们可以得到结论：若两点双有交，则交点一定是割点。

现在不妨思考一下，是否割点一定是多个点双的交点。对于一个割点，删掉它后一定存在原本连通的 \(u, v\) 不连通，而 \(u, v\) 显然不能位于同一个点双内，故结论成立。

综合上述加粗性质，我们可以得到一条边恰属于一个点双。

和边双一样，我们仍然有性质：对于 \(n \geq 3\) 的点双内任意一点 \(u\)，存在经过 \(u\) 的简单环。

Menger 定理

我们考虑将边双连通的的结论 \(2\) 拓展到简单环上。即我们证明对于点双内任意两点 \(u, v\) 存在经过 \(u, v\) 的简单环。

回路证明的是边不相交，现在我们要证明点不相交，自然可以想到进行拆点。

对于点 \(u\) 拆成 \(u_{in}, u_{out}\)，所有 \(u\) 的邻点 \(v\) 向 \(u_{in}\) 连容量为 \(+\infty\) 的边，\(u_{out}\) 向所有邻点 \(v\) 连容量为 \(+\infty\) 的边。而 \(u_{in} \to u_{out}\) 有一条容量为 \(1\) 的边。这保证了最小割只会割到点。

则 \(s \to t\) 的最大流 \(f\) 表示存在 \(f\) 条路径使得除 \(s, t\) 外的点不相交，且 \(f\) 取到了最大值。最小割同理。特别地当 \(s, t\) 相邻时 \(f = +\infty\)，因为不存在第三点使得删去后 \(u, v\) 不连通。

于是我们证明了开头的结论。

Menger 定理（边形式）：

对于无向图 \(G\) 上任意不同的两点 \(u, v\)，使得 \(u, v\) 不连通所需删去的边的数量的最小值等于 \(u, v\) 之间边不相交的迹的数量的最大值。

Menger 定理（点形式）：

对于无向图 \(G\) 上任意不同且不相邻的两点 \(u, v\)，使得 \(u, v\) 不连通所需删去的点数的最小值等于 \(u, v\) 之间点不相交的路径数量的最大值。

• 局部边连通度：使得 \(u, v\) 不连通所需删去的边的最小值为 \(u, v\) 的局部边连通度，记作 \(\lambda(u, v)\)。
• 局部点连通度：对于 \((u, v) \not \in E\)，使得 \(u, v\) 不连通所需删去的点的数量的最小值，记作 \(\kappa(u, v)\)。
• \(k\)-边连通：若 \(\lambda(u, v) \geq k\)，则称 \(u, v\) 是 \(k\)-边连通的。
• \(k\)-点连通：若 \(\kappa(u, v) \geq k\)，则称 \(u, v\) 是 \(k\)-点连通的。

局部点/边连通都可以通过 Menger 定理进行转换。

• 全局边连通度：\(\lambda(G) = \underset{u \not = v}{min} \{\lambda(u, v)\}\)。
• 全局点连通度：\(\kappa(G) = \underset{u \not = v \wedge (u, v) \not \in E}{min} \{\kappa(u, v)\}\)。
• \(k\)-边连通图：对于 \(k \in \N\)，若 \(\lambda(G) \geq k\)，则称 \(G\) 是 \(k\)-边连通图。
• \(k\)-点连通图：对于 \(k \in \N\)，若 \(\kappa(G) \geq k\)，则称 \(G\) 是 \(k\)-点连通图。

会发现边（点）双连通图也就是 \(2\)-边（点）连通图。

根据 Menger 定理，一张图不存在割点（边）等价于对于任意两点 \(u, v\)，存在经过 \(u, v\) 的回路（环）。

接下来不妨将点双与边双合起来讨论，令 \(n \geq 3\)。

若图没有割点，则一定没有割边，这是好证明的。因此任何边双满足的性质，点双一定满足。因此点双的性质一定比边双强，从前文即可看出。环一定是回路，回路不一定是环（回路可以重复点，环不行）。

所以有一些点双的拓展性质（不给出证明了）。

性质 \(1\)：\(n \geq 3\) 点双中任意一点 \(x\) 与一边 \(e\)，存在经过 \(x, e\) 的简单环。

性质 \(2\)：\(n \geq 3\) 点双中任意不同两点 \(x \not = y\) 与一边 \(e\)，存在 \(x \to e \to y\) 的简单路径。

性质 \(3\)：\(n \geq 3\) 点双中任意不同三点 \(x, y, z\)，存在 \(x \to z \to y\) 的简单路径。

割点求法

定义 \(dfn_u\) 为图的 dfs 序，\(low_u\) 为 \(u\) 或 \(u\) 的子树最多能通过一条非树边走到的最小 \(dfn\)。

则点 \(u\) 为割点的条件为存在至少一个儿子 \(v\) 满足 \(low_v \geq dfn_u\)。但会发现对于第一个结点该判定失效，容易发现对于第一个结点来说如果在搜索树中同时拥有两个儿子则一定是割点，因为其中一个儿子和另一个无法连通。

割边求法

与割点类似，我们要判定 \(low_v > dfn_u\)，并且不需要专门处理第一个结点。

但一个问题是可能存在重边。一般来说如果加入了一条边 \((u, v)\) 则 \((v, u)\) 为非树边，可如果存在边 \((v, u)\) 就会错误地判定。我们不妨记录一下点 \(u\) 是从哪条边来的。对于 vector 存图可以直接记录边的编号，对于链式前向星 \(e\) 与 \(e \oplus 1\) 是两条对应的边。

边双连通分量求法

考虑在判断完割边的基础上，对于每个连通块 dfs 一边即可。

当然也可以考虑使用栈来维护这个东西。

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++ timestamp;
    for (auto [v, id]: G[u]) {
        if (!dfn[v]) {
            tarjan(v, id); 
            if (dfn[u] < low[v]) bridge[id] = 1;
            low[u] = min(low[u], low[v]);
        } else if (id != fa) low[u] = min(low[u], dfn[v]);
    }
}

void dfs(int u, int bccid) {
    bcc[bccid].push_back(u); vis[u] = 1, b[u] = bccid;
    for (auto [v, id] : G[u]) {
        if (bridge[id] || vis[v]) continue;
        dfs(v, bccid);
    }
}

点双连通分量求法

例题

P3469

显然如果删掉一个割点点会分成若干个连通块，则对于一个割点它的答案为 \(\sum_{i = 1}^k sz_i \times (n - sz_i)\)。注意由于割点没被删除所以割点本身也是一个块。

P2860

翻一下题面就是问最少加几条边使得图是一个边双。

考虑边双缩点后会得到若干个叶子，对于奇数个叶子的情况，将任意一个叶子与树内度数 \(\geq 3\) 的点连一条边（如果不存在说明是链，不满足叶子为奇数），转化到偶数个叶子的情况。

对于偶数个叶子的情况，先任意两两匹配，然后如果存在 \((u, v)\) 为割边则对于断开边后 \(u\) 和 \(v\) 分别所属的连通块内进行调整即可。

所以我们得到答案为叶子数量除以 \(2\) 上取整。

CF51F

蛮困难的。

要求无环，所以先边双缩点，通过操作搞成一个森林。先用树的个数减一次操作将森林合成一棵树。

然后考虑我们此时选出了一条路径 \(P\)，那么所有距离 \(P\) 距离超过 \(1\) 的点都要进行一次操作。此时画点图观察一下会发现相当于将所有的叶子留下，叶子到 \(P\) 的路径全部合并起来。所以贡献为 \(n - |P| - L\)，\(L\) 为叶子数量。

想想怎么选路径 \(P\)，直觉上应该选树的直径，原因也很简单，因为 \(P\) 的长度拓展 \(1\) 至多减少一个叶子，所以一定是优秀的。