双连通分量 学习笔记

简言之，在无向图中找所有的简单环应当用 Tarjan。 ## 无向图中连通性的概念 对于无向图 $G=(V,E)$，若存在一条路径从 $u$ 到 $v$，则称 $u$ 和 $v$ 互相**连通**（*connected*）。 若对任意 $u,v\in V$，都有 $u$ 和 $v$ 连通，则我们称 $G$ 是一张**连通图**。（*connected graph*） 若有连通图 $F\subseteq G$，且不存在另一个连通图 $H$ 使 $F\subsetneqq H\subseteq G$，则称 $F$ 是 $G$ 的**连通块/连通分量**（*connected component*）或**极大连通子图**。 对于无向图 $G=(V,E)$，若无论删去 $E$ 中的哪条边（只能一条），都有 $u,v$ 仍然连通，则称 $u$ 和 $v$ **边双连通**（*edge double connected*）。 同样若无论删去 $V$ 中的哪个点（只能一个）及其与相连的所有边，都有 $u,v$ 仍然连通，则称 $u$ 和 $v$ **点双连通**（*vertex double connected*）。 易证：**边双连通具有传递性，但点双连通不具有传递性**。 类似上面的定义可以导出**边双连通图**、**点双连通图**、**边双连通分量**、**点双连通分量**的定义。 其中边双连通分量（*e-DCC*）和点双连通分量（*v-DCC*）合称**双连通分量**（*DCC*）。 不过要注意：***e-DCC* 中不包含割边，但 *v-DCC* 中会多次包含割点**。 **性质：无向图 $G$ 是点双连通图，当且仅当 $|V|\le 2$ 或任意两点包含在至少一个简单环之中**。 证明：$|V|\le 2$ 的情况显然，第二个条件的充分性也易证，下证其必要性。 假如存在 $u,v$ 不在同一个简单环之中，则从 $u$ 到 $v$ 的所有路径一定有一个除两端点以外的交点。 删去此交点则 $u$，$v$ 不连通，形成矛盾。故必要性得证。 另外，若删去连通图 $G$ 中的某条边能使 $G$ 不连通，则称此边为 $G$ 的**割边**（*cut edge*）/**桥**（*bridge*）。 同样，若删去连通图 $G$ 中的某个点能使 $G$ 不连通，则称此点为 $G$ 的**割点**（*cut vertex*）。 ## 树上差分法求割点、割边 树上差分法理解较为容易，复杂度也和 *Tarjan* 无异。 我们从任意一个结点出发 DFS。如果从一个结点出发的一条边到达了一个已经访问过的结点，那么很显然这个环内的所有边都不是割边。 也就是说，我们需要把路径上的边标记为“不是割边”。由于可以离线计算，我们可以用树上差分在 $\Theta(n)$ 内解决。 最后剩下的未被标记的边都是割边。 求割点同理，先需要经过一步点边互换的操作，然后把所有非树边的路径上的新点连到一起。 那么，一个点是割点当且仅当与其相连的所有边在新图中对应的新点都属于同一个连通块。 求完割边、割点后还可以进行缩点。懒得放代码了。 ## Tarjan 算法求割点、割边 和有向图中的 *Tarjan* 类似，我们**需要找环**。同样，我们维护每个点的 $dfn$ 值、$low$ 值。 区别于有向图中 $low$ 的定义，无向图中的 $low(x)$ 表示从 $subtree_x$ 出发**不经过树边**所能达到的最小的 $dfn$ 值。 *Tarjan* 算法的主过程 $\texttt{tarjan(x)}$ 如下： 1. 记录 $dfn(x)$ 的值，先赋值 $low(x)$ 为 $dfn(x)$。 2. 枚举每条从 $x$ 出发的点 $(x,y)$。 3. 若 $y$ 未被访问过，那么 $(x,y)$ 为树边。执行 $\texttt{tarjan(y)}$，用 $low(y)$ 去更新 $low(x)$。 4. 若 $y$ 已经被访问过且 $y$ 在栈中，那么用 $dfn(y)$ 去更新 $low(x)$。（这里细节见下） 5. 回溯时，若有 $low(x)>dfn(fa_x)$，则说明从 $x$ 出发向下无论怎么搜都搜不到 $fa_x$ 及以上的点。这时我们判断边 $(x,fa_x)$ 为桥； 若有 $low(x)\geq dfn(fa_x)$，则说明从 $x$ 出发向下无论怎么搜都搜不到 $fa_x$ 以上的点。这时我们判断 $fa_x$ 为割点。 **但是**，判断割点是需要注意，如果 $x$ 是搜索树的根，那么对 $y\in son_x$，无论如何都会有 $low(y)\geq dfn(fa_y)$。这是不正确的。 这说明，如果 $x$ 是搜索树的根，那么需要有至少两个 $y$ 满足 $low(y)\geq dfn(fa_y)$ 才能判断 $x$ 为割点。 在第 4 步中，特别要注意的一点是： - 求割边时用 $dfn(y)$ 去更新和用 $low(y)$ 是等效的，因为它们和 $dfn(x)$ 的大小关系是一致的。 - 求割点时如果按照下面实现中的写法，是只能用 $dfn(x)$ 去更新的。 因为如果用 $low(x)<dfn(x)$，那么这会使 $low(y)$ 也变为 $<dfn(x)$。其意义是 $y$ 通过一条非树边到达 $x$，然后从 $x$ 再出发到达早于 $x$ 的节点，这是不合法的。 当然，如果更新时加以判断，使 $y\ne fa_x$，那么二者等价。 ## Tarjan 算法的实现 - [T103481 【模板】割边](https://www.luogu.com.cn/problem/T103481) 这题不是主题库的题，不过确实是一个不错的板子。 这里由于我们要避免搜回去，但是图又可能存在重边，因此我们采取**记录搜过来的边**的形式。 加边前必须赋初值`tot=1`。 ```c++ void tarjan(int x,int pre) { dfn[x]=low[x]=++cnt; for(int i=head[x];i;i=Next[i]) { int y=ver[i]; if(!dfn[y]) { tarjan(y,i); low[x]=min(low[x],low[y]); if(low[y]>dfn[x]) ans++; } else if((i^1)!=pre) low[x]=min(low[x],dfn[y]); } } ``` [Code](https://www.luogu.com.cn/record/54424132) - [P3388 【模板】割点（割顶）](https://www.luogu.com.cn/problem/P3388) 割点的板子。这里由于判断是非严格的，那么我们无须记录父亲。 但如上所述，**必须用 $dfn(x)$ 去更新**。而且要注意每个点至多被加入一次。 ```c++ void tarjan(int x) { dfn[x]=low[x]=++cnt; int cur=0; bool cut=false; for(int i=head[x];i;i=Next[i]) { int y=ver[i]; if(!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]&&!cut) { cur++; if(x!=rt||cur>=2) id[++res]=x, cut=true; } } else low[x]=min(low[x],dfn[y]); } } ``` [Code](https://www.luogu.com.cn/record/54426329) - [B3610 [图论与代数结构 801] 无向图的块](https://www.luogu.com.cn/problem/B3610) 求 *e-DCC* 太简单，只需要求出所有的桥后删去，大力 DFS 求连通块。这里只说明如何求 *v-DCC*。 我们维护一个栈，在开始 $\texttt{tarjan}(x)$ 过程时将 $x$ 压入栈，每次发现 $low(y)\geq dfn(x)$ 时不断弹这个栈直到 $y$ 被弹出，最后加入 $x$ 本身。 ```c++ void tarjan(int x) { dfn[x]=low[x]=++cnt; st[++top]=x; for(int i=head[x];i;i=Next[i]) { int y=ver[i]; if(!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]) { res++; while(st[top]!=y) { dcc[res].push_back(st[top]); top--; } dcc[res].push_back(st[top]);//y top--; dcc[res].push_back(x); } } else low[x]=min(low[x],dfn[y]); } } ``` 在主函数中，由于这题**不把**单个孤立点算作 *v-DCC*，我们要略加特判。 ```c++ fo(i,1,n) if(!dfn[i]) { tarjan(i); if(top>1) { res++; while(top>0) { dcc[res].push_back(st[top]); top--; } } top=0; } ``` [Code](https://www.luogu.com.cn/record/54434094) - [P3469 [POI2008]BLO-Blockade](https://www.luogu.com.cn/problem/P3469) 我们遍历出所有的连通块，记第 $i$ 个的大小为 $siz_i$。 不删点时，连通块之间无法互相到达。计算出不删点时的答案 $res$： $$ res=\sum_{i=1}^n\sum_{j=1}^{i-1} 2\times siz_i\times siz_j $$ 这可以用前缀和优化在 $\Theta(n)$ 内计算出。 一方面，显然当 $x$ 不是割点时，答案 $ans_x=res$； 另一方面，当 $x$ 是割点时，答案 $ans_x$ 除了 $res$ 以外还需要加上连通块内产生的贡献。 设割点 $x$ 把这个连通块分为 $cnt$ 块，每块的大小为 $a_i$。那么块内的贡献即为： $$ res=\sum_{i=1}^{cnt}\sum_{j=1}^{i-1} 2a_ia_j $$ DFS 的过程中直接计算即可。 [Code](https://www.luogu.com.cn/record/54467648)