[学习笔记] tarjan求割点+割边+强连通分量+缩点
前言
之前确实是写过一篇，但是现在看了看，写的真的不太行而且也不全面，所以重写一篇，然后把之前的隐掉了（话说这篇竟然是迄今为止，我博客中阅读数最多的
无向图的割点和桥（割边）
基础概念
时间戳
\(tarjan\) 中的 \(dfn\) 数组在图的深度优先搜索中，按照每个节点第一次被访问的时间排序，其还有另一个名称“\(dfs\)序”
追溯值
\(tarjan\) 中的 \(low_u\)数组，设 \(Subtree_u\) 表示搜索树中以 \(x\) 为根的子树，\(low_u\) 定义是以下结点的\(dfn\)的最小值：
- \(Subtree_u\) 中的节点；
- 从 \(Subtree_u\) 通过一条不在搜索树上的边能到达的结点
判定法则
割边
无向边 \((u,v)\) 是桥,当且仅当搜索树上存在 \(u\) 的一个子节点 \(v\) ，满足：
\[low_v>dfn_u \]这个公式说明了，在不经过 \((x,y)\) 这条边的情况下，从 \(Subtree_v\) 出发，无论如何都无法走到比 \(u\) 更早访问到的
点，换句话说，\(Subtree_v\) 形成了一个闭环，那么把 \((u,v)\) 这条边去掉就会出现不连通的子图了
现在我们还得知道一句话，这句话对于理解 \(tarjan\) 的代码有重要作用：
桥一定是搜索树上的边，并且一个简单环中的边一定都不是桥
如果不是搜索树上的边，那么就会形成一个环，但是环去掉一条边还是连通的
code
#include
#include
#include
#include
using namespace std;
const int N=2e5+10;
int ver[N],tot=1,head[N],nxt[N],n,m,dfn[N],dfstime,low[N];
bool bri[N];
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void add(int x,int y){
ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
void tarjan(int u,int inedge){
dfn[u]=low[u]=++dfstime;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]) bri[i]=bri[i^1]=1;
}
else if(i!=(inedge^1)) low[u]=min(low[u],dfn[v]);
}
}
int main(){
n=read();m=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
add(x,y);add(y,x);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);//图可能不是连通的
for(int i=2;i 我们可以注意到这一段代码
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);//通过递归更新
if(low[v]>dfn[u]) bri[i]=bri[i^1]=1;
}
else if(i!=(inedge^1)) low[u]=min(low[u],dfn[v]);
首先我们运用了成对存储，因为连向父亲的边很明显是不能更新 \(low\) 的，但是由于父亲的 \(dfn\) 肯定比子结点更新
被更新到，所以前面不需要判断
这段代码的含义就是我们之前说的更新追溯值的两种情况，\(if\) 对应的就是通过搜索树内的子结点来更新，而
\(else\) \(if\) 对应的则是通过非搜索树上的边来更新，因为搜索树上只有树边和返祖边
注意到在 \(else\) 的情况里我们没有去使用割点的判断法则，因为这里是非搜索边的情况，这可以通过桥一定是搜索
树上的边，并且一个简单环中的边一定都不是桥来解释，所以就没有判断的必要了
割点
若 \(u\) 不是搜索树的根节点，若 \(u\) 节点是割点，那么当且仅当搜索树上存在 \(u\) 的一个儿子节点 \(v\) ，满足
\[low_v\ge dfn_u \]特别地，若根是割点当且仅当根至少有两个子结点满足上述条件
判定法则的证明和割边差不多，所以不多赘述，但是它们的不同之处还得讲讲，一个点要成为割点，那么它肯定
连接了至少两个点，对于非更根节点，如果它是叶子节点，那么也就不存在它的搜索树了，但是对于根节点，它
是有可能存在只有一个，下图就是一个例子
很明显每个点的 \(low\) 都是 \(1\)，对于根来说满足了上述条件但是根不能成为割点
code
#include
#include
#include
#include
using namespace std;
const int N=2e5+10;
int ver[N],tot=1,head[N],nxt[N],n,m,dfn[N],dfstime,low[N],cut[N],root;
bool bri[N];
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void add(int x,int y){
ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
void tarjan(int u){
dfn[u]=low[u]=++dfstime;
int flag=0;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
flag++;
if(u!=root||flag>1) cut[u]=1;
}
}
else low[u]=min(low[u],dfn[v]);
}
}
int main(){
n=read();m=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
if(x==y) continue;
add(x,y);add(y,x);
}
for(int i=1;i<=n;i++) if(!dfn[i]) root=i,tarjan(i);//图可能不是连通的
for(int i=1;i<=n;i++)
if(cut[i]) cout< 注意到这段代码
low[u]=min(low[u],dfn[v])
\(Q:\) 不能是 \(low[u]=min(low[u],low[v])\) 吗？
\(A:\) 因为我们对于第二情况的定义是“从 \(Subtree_u\) 通过一条不在搜索树上的边能到达的结点“，所以只能多走一条
具体的例子可以看下面一种情况：
如果按提问的方法写的话 \(low_5\) 就会为 \(1\)，那么由于 \(low_5=3\) 而判断出来的割点 \(3\) 就判断不出来了
能用 \(low_u\) 更新的前提是 \(Subtree_u\) 都被搜完了，其中 \(tarjan(v);\) 保证了这个。
强连通分量及缩点
基础概念
强连通分量
给定一张有向图，若对于图中任意两个节点，都有相互抵达的路经，则称该有向图是“强连通图”，而强连通分量
指的是“极大”的强连通图
DFS 生成树
这是很重要的一个概念
（图片来自 OI wiki）
有向图的 DFS 树主要有4种边 \((x,y)\) ：
-
树边：图中黑色的边，即搜索树上的边，\(x\) 是 \(y\) 的父亲
-
前向边：图中绿色的边，\(x\) 是 \(y\) 的祖先
-
后向边：也叫反祖边，是图中红色的边，即指向祖先的边
-
横叉边：它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先，它
一定满足 \(dfn_x>dfn_y\) ，也就是起点大于终点
我们考虑 DFS 生成树与强连通分量之间的关系。
如果结点 \(u\) 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树
中以 \(u\) 为根的子树中。结点 \(u\) 被称为这个强连通分量的根。
反证法：假设有个结点 \(v\) 在该强连通分量中但是不在以 \(u\) 为根的子树中，那么 \(u\) 到 \(v\) 的路径中肯定有一条离开
子树的边。但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和
\(u\) 是第一个访问的结点矛盾了。得证。（以上内容均摘自 OI wiki）
tarjan求强连通分量
\(low_u\) 表示：能够回溯到的最早的已经在栈中的结点（和割点的不同之处，在栈中），所以 \(low_u\) 定义为以下结
点的 \(dfn\) 的最小值：\(Subtree_u\) 中的结点；从 \(Subtree_u\) 通过一条不在搜索树上的边能到达的结点
那么我们考虑 \(3\) 种情况：
-
\(v\) 未被访问过：继续对 \(v\) 进行深度优先搜索，然后在回溯的时候用 \(low_v\) 更新 \(low_u\)，因为它们之间存在直接
路经，所以 \(v\) 能到达的 \(u\) 一定也能到达
-
\(v\)被访问过，已经在栈中：根据定义第二条，我们能且只能用 \(dfn_v\) 去更新 \(low_u\)
-
\(v\)被访问过，不再栈中：出栈就说明，其所在连通分量已被处理，不用再操作了
若从 \(x\) 回溯前，有：
\[low_u=dfn_u \]则从 \(x\) 到栈顶的所以结点构成一个强连通分量
code
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int N=2e5+10;
int cut[N],head[N],ver[N],nxt[N],dfn[N],low[N],dfstime,n,m,c[N],ins[N],vis[N],top,tot,sta[N],cnt;
vector scc[N];
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void add(int x,int y){
ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
void tarjan(int u){
dfn[u]=low[u]=++dfstime;
sta[++top]=u,ins[u]=1;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
cnt++;int v;
while(u!=v){
v=sta[top--],ins[v]=0;
c[v]=cnt,scc[cnt].push_back(v);
}
}
}
signed main(){
n=read();m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();
add(u,v);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
cout< 缩点
其实理解了如何求强连通分量就很好理解缩点了
for(int i=1;i<=m;i++){
int x=c[from[i]],y=c[ver[i]];
if(x!=y) adde(x,y);
}
在上面的代码上加上这么一段，差不多就好可
学习资料
OI wiki