\(Tarjan\)算法在无向图中的应用
无向图的割点与桥
设无向连通图\(G=(V,E)\),
若对于\(x \in V\),从图中删去节点\(x\)以及所有与\(x\)关联的边之后,\(G\)分裂成两个或两个以上不相连的子图,则称\(x\)为\(G\)的割点.(简单定义:删掉这个点之后,图不再连通,则这个点是割点).
若对于\(e \in E\),从图中删去边\(e\)之后,\(G\)分裂成两个不相连的子图,则称\(e\)为\(G\)的桥或割边.(简单定义:删掉这条边之后,图不再连通,则这条边是割边)
在无向图中任选一个节点出发进行深度优先遍历，每个点只访问一次.所有发生递归的边\((x,y)\)构成一棵树,我们把它称为“无向连通图的搜索树”，当然一般无向图（不一定连通）的各个连通块的搜索树构成无向图的“搜索森林”.
在图的深度优先遍历的过程中，按照每一个节点第一次被访问的时间顺序，给予\(n\)个节点\(1~n\)的整数标记，该标记就被称为“时间戳”.记为\(dfn[x]\)(简单定义:\(dfs\)的遍历顺序)
“追溯值”\(low[x]\).设\(subtree(x)\)表示搜索树中以\(x\)为根的子树.\(low[x]\)定义为以下两种节点的时间戳最小值：
1.\(subtree(x)\)中的节点.
2.通过一条不在搜索树上的边，能够到达\(subtree(x)\)中的节点（就是与搜索树中以\(x\)为根的子树以不在搜索树上的边相连的节点）.
割边判定法则:无向边\((x,y)\)是割边，当且仅当搜索树上存在\(x\)的一个子节点\(y\)，满足:\(dfn[x]<low[y].\)(很好理解,\(y\)在不经过\((x,y)\)这条边的前提下,无论如何都无法到达x或比x更早访问的节点,所以切掉\((x,y)\)这条边之后,\(x,y\)就被分割到了两个部分.)
inline void add(int a,int b){
nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void tarjan(int u,int in_edge){
dfn[u]=low[u]=++timeclock;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(!dfn[v]){//搜索树上v是u的子节点
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v])bridge[i]=bridge[i^1]=1;//标记是否是桥边
}
else if(i!=(in_edge^1)){//无向边(u,v)不在搜索树上
low[u]=min(low[u],dfn[v]);
}
}
}
int main(){
n=read();m=read();tot=1;//注意这个tot的初始值是1不是0
for(int i=1;i<=m;++i){
a[i]=read();b[i]=read();
add(a[i],b[i]);add(b[i],a[i]);
}
for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i,0);
...
return 0;
}
割点判定法则:若\(x\)不是搜索树的根节点(深度优先遍历的起点),则\(x\)是割点当且仅当搜索树上存在\(x\)的一个子节点\(y\),满足:\(dfn[x]<=low[y]\).
特别地,如果\(x\)是搜索树的根节点,那么\(x\)是割点当且仅当搜索树上存在至少两个子节点满足上述条件.
inline void tarjan(int x){
dfn[x]=low[x]=++timeclock;
int child=0;//记录子节点数量
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y]){
child++;
if(x!=root||child>=2)cut[x]=1;//标记x是割点
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int main(){
...
for(int i=1;i<=n;i++)
if(!dfn[i])root=i,tarjan(i);
...
}
无向图的双连通分量
若一张无向连通图不存在割点,则称它为"点双连通分量".若一张无向连通图不存在桥,则称它为"边双连通分量".无向图的极大点双连通子图称作"点双连通分量(\(v-DCC\))",无向图的极大边双连通子图称作"边双连通分量(\(e-DCC\))."
边双连通分量\((e-DCC)\)的求法:先求出图中所有的桥(割边),把桥边都删掉之后,图就会分成若干个连通块,每个连通块都是一个"边双连通分量".
代码建立在已经用\(Tarjan\)标记了所有的桥边的情况下:
inline void dfs(int x){
belong[x]=dcc;//编号为x的节点属于第dcc个边双连通分量
for(int i=head[x];i;i;=nxt[i]){
int y=to[i];
if(belong[y]||bridge[i])continue;
//如果点y已经遍历过 或者 (x,y)之间的边是桥边,则跳过
dfs(y);
}
}
int main(){
...
for(int i=1;i<=n;++i)
if(!belong[i]){//划分每个点属于哪个边双连通分量
++dcc;
dfs(i);
}
...
}
边双连通分量\((e-DCC)\)的缩点:在上述求出边双连通分量\((e-DCC)\)并划分出每个连通块之后,把每个\(e-DCC\)都看作一个节点,然后桥边看作连接节点之间的边,则原来的无向连通图构成了一棵树,这就是缩点操作了.具体代码实现的话,就枚举每条边,如果两个端点不在同一个\(e-DCC\)内,那么这条边就加入新的图中.
点双连通分量\((v-DCC)\)的求法:
1.若某个节点为孤立点,则它自己单独构成一个\(v-DCC\).
2.除了孤立点之后,\(v-DCC\)的大小至少为2.
3.桥不属于任何\(v-DCC\),但是割点可能属于多个\(v-DCC\).
inline void tarjan(int x){
dfn[x]=low[x]=++tim;st[++top]=x;
if (x==root&&head[x]==0){
dcc[++cnt].push_back[x];
return;
}
int flag=0;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
flag++;
if(x!=root||flag>1)cut[x]=true;
cnt++;int z;
do{
z=st[top--];
dcc[cnt].push_back[z];
}while(z!=y)
dcc[cnt].push_back[x];
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int main(){
...
for(int i=1;i<=cnt;i++)
for(int j=0;j<dcc[i].size();j++)
printf("%d", dcc[i][j]);
...
}
点双连通分量\((v-DCC)\)的缩点:设图中有\(p\)个割点和\(t\)个\(v-DCC\),那么我们建立一张包含\(p+t\)个节点的新图,把每个\(v-DCC\)和每个割点作为新图中的节点,并在每个割点与包含它的所有\(v-DCC\)之间连边.这个新图就是一棵树.
代码建立在上面求点双连通分量\((v-DCC)\)的基础之上:
num=cnt;
//cnt表示的是图中v-DCC的个数
for(int i=1;i<=n;++i)
if(cut[i])new_id[i]=++num;
//给每个割点一个新的编号,从cnt+1开始
tot_c=1;
//重新建图的边的总数,从1开始的技巧不说了
for(int i=1;i<=cnt;++i)
for(int j=0;j<dcc[i].size();++j){
int x=dcc[i][j];
if(cut[x]){//在割点和包含它的v-DCC之间连边
add_c(i,new_id[x]);
add_c(new_id[x],i);
}
else belong[x]=i;//割点之外的点,只会属于一个v-DCC
}
\(Tarjan\)算法在有向图中的应用
有向图的强连通分量:
强连通:在一个有向图\(G\)里，设两个点\(a,b\)，由\(a\)有一条路可以走到\(b\)，由\(b\)有一条路可以走到\(a\)，我们就叫这两个顶点\((a,b)\)强连通.策划那个这个有向图是强连通图.
有向图的极大强连通子图称为"强连通分量",简记为\(SCC\).
void add(int a,int b){
nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
void tarjan(int u){
dfn[u]=low[u]=++timeclock;
st[++top]=u;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!color[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){//满足强连通分量的条件
color[u]=++cnt;
while(st[top]!=u){
color[st[top]]=cnt;
top--;
}
top--;
}
}
int main(){
n=read();m=read();
for(int i=1;i<=m;i++){
int a,b;
a=read();b=read();
add(a,b);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
//至于最后输出什么,就看题目求什么了;
//总之,我们已经得到了强连通分量的个数cnt
//每个点分别属于哪个强连通分量(color数组记录)
return 0;
}
把强连通分量缩点会得到一张有向无环图\(DAG\).
for(int x=1;x<=n;++x)
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(color[x]==color[y])continue;
add_c(color[x],color[y]);
//如果这条有向边的两个端点不属于同一个强连通分量
//则在这两个强连通分量之间连边,边的方向保持不变
}
有向图的必经点与必经边:
给定一张有向图,起点\(S\),终点\(T\).若从\(S\)到\(T\)的每条路径都经过一个点\(x\),则称点\(x\)是有向图中从\(S\)到\(T\)的必经点.
从\(S\)到\(T\)的每条路径都经过一条边\((x,y)\),则称这条边是有向图中从\(S\)到\(T\)的必经边或桥.
计算有向无环图\(DAG\)中的必经点与必经边:
1.在原图上按照拓扑序进行动态规划,求出起点\(S\)到图中每个点\(x\)的路径条数\(fs[x]\).
2.在反图上再次按照拓扑序进行动态规划,求出图中每个点\(x\)到终点\(T\)的路径条数\(ft[x]\).
显然,\(fs[T]\)表示从\(S\)到\(T\)的路径总条数.根据乘法原理:
1.对于一个点x,若\(fs[x]*ft[x]=fs[T]\),则\(x\)是有向无环图上\(S\)到\(T\)的必经点.
2.对于一条有向边\((x,y)\),若\(fs[x]*ft[y]=fs[T]\),则\((x,y)\)是有向无环图上\(S\)到\(T\)必经边.