参考资料：OI Wiki、初级图论 by Alex_Wei、高级图论 by Alex_Wei
无向图连通性
一些定义
若无向图 \(G\) 中任意不同两点 \((u,v)\) 都有路径可达，称 \(G\) 为一个 连通图，若 \(G\) 的一个子集 \(H\) 满足不存在连通子图 \(G'\) 满足 \(H\subseteq G'\)，则 \(H\) 为一个 连通块/连通分量，也即极大连通子图。
若无向图 \(G\) 中存在一个点集 \(V'\) 满足删去这些点以及连边后，原图的连通分量个数会增加，称点集 \(V'\) 为一个 点割集，特别地，当 \(V'\) 中只含一个节点 \(u\) 时，称节点 \(u\) 为 割点。
若无向图 \(G\) 中存在一个边集 \(E'\) 满足删去这些边后，原图的连通分量个数会增加，称边集 \(E'\) 为一个 边割集，特别地，当 \(E'\) 中只含一条边 \((u,v)\) 时，称边 \((u,v)\) 为 割边/桥。
若一个连通图中不含割点，则该连通图 点双连通；若一个连通图中不含割边，则该连通图 边双连通。类比连通分量的定义，同样有 点双连通分量 与 边双连通分量。
割点
使用 Tarjan 算法。
在无向图 DFS 树中，横叉边是不存在的，因此每个 \(u\) 的每个儿子 \(v_i\) 的子树 \(T(v_i)\) 都是两两独立的，这个性质在后续会不断用到。
割点不为 DFS 树根时
对非树根 \(u\) 讨论，其作为割点的充要条件是删去 \(u\) 后存在一棵子树 \(T(v_i)\) 成为连通块，也就是存在一棵子树 \(T(v_i)\)，其内部的任意节点是无法在不经过 \(u\) 的前提下去到子树外。
思考可以不经过 \(u\) 去到子树外的一颗子树 \(T(v_i)\)，这条路径应当是若干 \(T(v_i)\) 内部的边与一条返祖边 \((w,f)\) 组成，由于 DFS 树中不含横叉边，则 \(f\) 应当是 \(u\) 的一个祖先，于是 \(\mathrm{dfn}(f)<\mathrm{dfn}(u)\)。
因此只需要维护 \(\mathrm{low}(v_i)\) 表示子树 \(T(v_i)\) 内所有节点中 只通过一条非树边 可以去到的最小 \(\mathrm{dfn}\) 值。
关于“只经过一条非树边”的设定
这样的设定足以满足我们对割点的探究，思考为什么更广泛的定义会出现错误。
原因在于一个割点可能对应多个点双连通分量，因此存在一个节点先后通过两条非树边到达割点再走到割点的祖先，此时就违背了刚才“不经过 \(u\)”的前提。
\(\mathrm{low}(u)\) 的计算方法如下：
-
初始设置为 \(\mathrm{dfn}(u)\)
-
当 \(v\) 未被访问时，是一条树边，更新 \(\mathrm{low}(u)=\min(\mathrm{low}(u),\mathrm{low}(v))\)
-
当 \(v\) 已被访问时，是一条返祖边或前向边，后者对答案无影响，根据对 \(\mathrm{low}(u)\) 的定义，更新 \(\mathrm{low}(u)=\min(\mathrm{low}(u),\mathrm{dfn}(v))\)。
于是当 \(u\) 存在一个子树 \(T(v_i)\) 满足 \(\mathrm{low}(v_i)\ge \mathrm{dfn}(u)\)，说明 \(u\) 是割点。
割点为 DFS 树根时
容易发现，当树根出现不只一棵子树时，两棵子树间唯一路径为经过根的路径，即此时根是割点。
点击查看代码
struct Graph{
vector<int> E[maxn];
inline void add_edge(int u,int v){
E[u].push_back(v);
E[v].push_back(u);
}
int rt;
int dfn[maxn],low[maxn],dfncnt;
bool vcut[maxn];
int cnt_vcut;
void Tarjan(int u){
dfn[u]=++dfncnt,low[u]=dfn[u];
int cnt_son=0;
for(int v:E[u]){
if(!dfn[v]){
++cnt_son;
Tarjan(v);
low[u]=min(low[u],low[v]);
if(u!=rt&&low[v]>=dfn[u]) vcut[u]=1;
}
else{
low[u]=min(low[u],dfn[v]);
}
}
if(u==rt&&cnt_son>1) vcut[u]=1;
if(vcut[u]) ++cnt_vcut;
}
inline void solve(){
for(int u=1;u<=n;++u){
if(!dfn[u]){
rt=u;
Tarjan(u);
}
}
printf("%d\n",cnt_vcut);
for(int u=1;u<=n;++u){
if(vcut[u]) printf("%d ",u);
}
printf("\n");
}
}G;
割边
割边一定是 DFS 树的非树边，在割点的基础上修改算法流程，注意到 \(T(v_i)\) 可以经过非树边返回 \(u\) 则 \((u,v_i)\) 并不属于割边，因此判断条件修改为：\(\mathrm{low}(v_i)>\mathrm{dfn}(u)\)。
且求割边不需要讨论根的问题。
有重边时用邻接表存图，\(cnt\) 从 \(2\) 开始记录，这样正反两条边的编号是异或关系，判断是不是同一条边即可。
点击查看代码
struct Graph{
struct edge{
int to,nxt;
}e[maxm<<1];
int head[maxn],cnt;
Graph(){
cnt=1;
}
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt;
}
int fa[maxn];
int dfn[maxn],low[maxn],dfncnt;
bool ecut[maxn];
int cnt_ecut;
void Tarjan(int u,int f,int id){
dfn[u]=++dfncnt,low[u]=dfn[u];
for(int i=head[u];i;i=e[i].nxt){
if(i==id) continue;
int v=e[i].to;
if(!dfn[v]){
Tarjan(v,u,i^1);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]) ecut[v]=1;
}
else{
low[u]=min(low[u],dfn[v]);
}
}
}
inline void solve(){
for(int u=1;u<=n;++u){
if(!dfn[u]){
Tarjan(u,0,0);
}
}
for(int u=1;u<=n;++u){
if(ecut[u]) ++cnt_ecut;
}
printf("%d\n",cnt_ecut);
for(int u=1;u<=n;++u){
if(ecut[u]) printf("%d %d\n",u,fa[u]);
}
}
}G;
边双连通分量
考虑一个简单粗暴的做法，先 Tarjan 求出所有割边之后暴力 DFS，但是很不优美。
我们使用一个同时求出割边并缩点的做法，具体利用一个栈，这个方法将在各种缩点中一直用到。
在访问到一个节点时将其加入栈，当 \((u,v)\) 为割边时（此时 \(v\) 内遍历完回溯至 \(u\)），设将其分成了 \(G_u,G_v\) 两个子图，考虑到子树间独立，\(G_v\) 内部的点都在 \(v\) 之前入栈，而在 \(G_v\) 内部其他边双连通分量都已经被从栈求出（设另一割边 \((x,y)\)，则 \(y\) 遍历完回溯 \(x\) 一定在这之前），因此栈中 \(v\) 以上的节点都属于 \(v\) 的边双连通分量。
于是暴力弹栈即可。
点击查看代码
struct Graph{
struct edge{
int to,nxt;
}e[maxm<<1];
int head[maxn],cnt;
Graph(){
cnt=1;
}
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt;
}
int dfn[maxn],low[maxn],dfncnt;
int st[maxn],top;
int ebcc[maxn],cnt_ebcc;
vector<int> EBCC[maxn];
void Tarjan(int u,int id){
dfn[u]=++dfncnt,low[u]=dfn[u];
st[++top]=u;
for(int i=head[u];i;i=e[i].nxt){
if(i==id) continue;
int v=e[i].to;
if(!dfn[v]){
Tarjan(v,i^1);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]){
++cnt_ebcc;
while(st[top]!=v){
ebcc[st[top]]=cnt_ebcc;
EBCC[cnt_ebcc].push_back(st[top]);
top--;
}
ebcc[v]=cnt_ebcc;
EBCC[cnt_ebcc].push_back(v);
top--;
}
}
else{
low[u]=min(low[u],dfn[v]);
}
}
}
inline void solve(){
for(int u=1;u<=n;++u){
if(!dfn[u]){
Tarjan(u,0);
++cnt_ebcc;
while(top){
ebcc[st[top]]=cnt_ebcc;
EBCC[cnt_ebcc].push_back(st[top]);
top--;
}
}
}
printf("%d\n",cnt_ebcc);
for(int i=1;i<=cnt_ebcc;++i){
printf("%ld ",EBCC[i].size());
for(int u:EBCC[i]){
printf("%d ",u);
}
printf("\n");
}
}
}G;
有向图连通性
一些定义
若有向图 \(G\) 中任意不同两点 \((u,v)\) 都有路径可达，称 \(G\) 为一个 强连通图，若 \(G\) 的一个子集 \(H\) 满足不存在连通子图 \(G'\) 满足 \(H\subseteq G'\)，则 \(H\) 为一个 强连通分量。
若将有向图 \(G\) 中所有边替换成无向边，得到一个连通图，则称 \(G\) 为一个 弱连通图，类比强连通分量，有 弱连通分量 的定义。
强连通分量
下面的介绍将类比无向图中边双连通分量缩点的算法流程。
有向图 DFS 的子树虽然不保证完全独立，依然满足所有的横叉边 \((u,v)\) 都有 \(\mathrm{dfn}(u)>\mathrm{dfn}(v)\)，这一性质会广泛用到。
下面来讨论三种非树边对连通性的影响：
-
前向边：没有任何影响，等价于树上路径。
-
返祖边：边的两端点之间形成一个简单的强连通分量，同时可以与其他强连通分量结合。
-
横叉边：可以到达时间戳更小的节点。
也就说有必要好好研究的就是横叉边，给出一个性质：若存在横叉边 \((u,v)\) 则 \(v\) 可达 \(u\) 当且仅当 \(v\) 可达 \(\operatorname{LCA}(u,v)\)。
充分性显然。
必要性考虑如何在不经过 \(\operatorname{LCA}(u,v)\) 的情况下到达 \(u\)，此时返祖边结合树边是无用的，似乎只能借助与横叉边，而显然横叉边 \((u,v)\) 的存在就代表着 \(u\) 所在子树的时间戳都大于 \(v\) 所在子树，且横叉边只能从较大时间戳到较小时间戳，因此横叉边也无法使用，于是得证。
若 \(u,v\) 同时存在一个强连通分量里，则这个强连通分量树上深度最小的点至少是 \(\operatorname{LCA}(u,v)\)，因此一个强连通分量深度最小的点只有一个。我们希望在这个点记录强连通分量。
一个点如果不是强连通分量中深度最小的点，则一定可以通过一系列的横叉边以及返祖边去到自己的祖先位置，而这个祖先位置就是强连通分量中最小的点。
于是我们继续定义 \(\mathrm{low}(u)\) 为 \(u\) 通过非树边可以去到的最小时间戳。
下面是更新 \(\mathrm{low}(u)\) 的方式：
-
初始设置为 \(\mathrm{dfn}(u)\)
-
当 \(v\) 未被访问时，是一条树边，更新 \(\mathrm{low}(u)=\min(\mathrm{low}(u),\mathrm{low}(v))\)
-
当 \(v\) 已被访问时且已经弹栈，不再更新
-
当 \(v\) 已经被访问且未弹栈，更新 \(\mathrm{low}(u)=\min(\mathrm{low}(u),\mathrm{dfn}(v))\)
关于已经弹栈后不更新
\(v\) 已经弹栈说明 \(v\) 不可达 \(\operatorname{LCA}(u,v)\)（当前还处于 \(\operatorname{LCA}(u,v)\) 子树中，已经弹栈说明不在统一强连通分量），于是到达 \(v\) 对 \(u\) 的连通性是没有意义的。
这样当 \(\mathrm{dfn}(u)=\mathrm{low}(u)\) 时，说明 \(u\) 是当前强连通分量的最小深度节点，类比上文边双连通分量的证明，此时栈顶到 \(u\) 的所有节点都属于该强连通分量。
关于未弹栈时更新的转移
这里写作 \(\mathrm{dfn}(v)\) 或 \(\mathrm{low}(v)\) 均可，不同与割点割边时对一次非树边的限制，这里更新主要目的是检验 \(u\) 是否是最小深度节点，只需要让 \(\mathrm{low}(u)<\mathrm{dfn}(u)\) 就可以。
点击查看代码
struct Graph{
vector<int> E[maxn];
inline void add_edge(int u,int v){
E[u].push_back(v);
E[v].push_back(u);
}
int dfn[maxn],low[maxn],dfncnt;
int st[maxn],top;
int scc[maxn],cnt_scc;
vector<int> SCC[maxn];
void Tarjan(int u){
dfn[u]=++dfncnt,low[u]=dfncnt;
st[++top]=u;
for(int v:E[u]){
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!scc[v]){
low[u]=min(low[u],dfn[v]);// or low[u]=min(low[u],low[v])
}
}
if(dfn[u]==low[u]){
++cnt_scc;
while(st[top]!=u){
scc[st[top]]=cnt_scc;
SCC[cnt_scc].push_back(st[top]);
top--;
}
scc[u]=cnt_scc;
SCC[cnt_scc].push_back(u);
}
}
inline void solve(){
for(int u=1;u<=n;++u){
if(!dfn[u]) Tarjan(u);
}
}
}G;