Tarjan 算法介绍及用法

Tarjan

简介：

• 这是一个有关图联通的算法，它基于dfs 在解决有环的有向图或无向图的问题时，很多算法不好是操作…
• 那么就先要将环进行缩点，将其转换为DAG（有向无环图）或一棵树，然后问题应会迎刃而解

常规操作：

具体用法：

常规的用法：缩点，割点，割边，点双，边双

缩点：
概念：化环为点
原理：通过栈来将环内存下，并在第二次访问到该环的根节点时，依次弹出，进行编号
模板（code）：

1.在有向图中：

void tarjan(int x){ dfn[x]=low[x]=++tim; stk[++top]=x; vis[x]=1; SREP(i,0,E[x].size()){ int y=E[x][i]; if(!dfn[y]){ tarjan(y); chkmin(low[x],low[y]); } else if(vis[y]) chkmin(low[x],dfn[y]); } if(dfn[x]==low[x]){ tot++; do{ Id[stk[top]]=tot; vis[stk[top]]=0; }while(x!=stk[top--]); } }

2.在无向图中：

void tarjan(int x,int f){ dfn[x]=low[x]=++tim; stk[++top]=x; vis[x]=1; bool flag=1; SREP(i,0,E[x].size()){ int y=E[x][i]; if(y==f && flag){flag=0;continue;} if(!dfn[y]){ tarjan(y,x); chkmin(low[x],low[y]); } else if(vis[y]) chkmin(low[x],dfn[y]); } if(dfn[x]==low[x]){ tot++; do{ Id[stk[top]]=tot; vis[stk[top]]=0; }while(x!=stk[top--]); } }

然而一般题目多是无向图，接下来都用无向图了…

割点：
概念：若删掉某点后，原连通图分裂为多个子图，则称该点为割点。
原理：若low[y]>=dfn[x],则x为割点。因为low[y]>=dfn[x]，则说明y通过子孙无法到达x的祖先。那么对于原图，去掉x后，必然会分成两个子图。

模板（code）：

void tarjan(int x,int f){ dfn[x]=low[x]=++tim; stk[++top]=x; bool flag=1; int child=0; SREP(i,0,E[x].size()){ int y=E[x][i]; if(y==f && flag){flag=0;continue;} if(!dfn[y]){ child++; tarjan(y,x); chkmin(low[x],low[y]); if(low[y]>=dfn[x]){ cut[x]=1; //该点为割点  } } else chkmin(low[x],dfn[y]); } if(!f && child==1)cut[x]=0;//注意初始点，特判  }

割边（桥）：
概念：删掉该边后，原图必然会分裂为多个子图。
原理：若low[y]>dfn[x],则边(x,y)为桥。由割点同理可得。但是由于可能存在重边，需要把一条无向边拆成的两条标号相同的有向边，记录每个点的父亲到它的边的标号，如果边(x,y)是x的后向边，就不能用dfn[u]更新low[v]。这样如果遍历完v的所有子节点后，发现low[y]=dfn[y]，说明x的后向边(x,y)为割边。
模板（code）：

void tarjan(int x,int f){ dfn[x]=low[x]=++tim; stk[++top]=x; bool flag=1; SREP(i,0,E[x].size()){ int y=E[x][i]; if(y==f && flag){flag=0;continue;} if(!dfn[y]){ child++; tarjan(y,x); chkmin(low[x],low[y]); if(low[y]>dfn[x]){ mark[x][y]=mark[y][x]=1; //该边为割边  } } else chkmin(low[x],dfn[y]); } }

点双（点双连通分量）：
概念：在求出所有的割点以后，把所有的割点删除，原图变成了多个连通块。
原理：在求割点的过程中就能把每个点双连通分支求出。通过栈存储双连通分支。在搜索图时，每找到一条后向边(非横叉边)，就把这条边加入栈中。如果遇到某时满足dfn[x]<=low(y)，说明x是一个割点，同时把边从栈顶一个个取出，直到遇到了边(x,y)，取出的这些边与其关联的点，从而组成一个点双，一般再用个容器存一下每个点双。
模板（code）：

void tarjan(int x,int f){ dfn[x]=low[x]=++tim; stk[++top]=x; vis[x]=1; bool flag=1; int child=0; SREP(i,0,E[x].size()){ int y=E[x][i]; if(y==f && flag){flag=0;continue;} if(!dfn[y]){ child++; tarjan(y,x); chkmin(low[x],low[y]); if(low[y]>=dfn[x]){ cut[x]=1; V[++tot].clear(); do{ vis[stk[top]]=0; Id[stk[top]]=tot; V[tot].pb(stk[top]); }while(y!=stk[top--]); V[tot].pb(x); solve();//解决该点双上的问题  } } else if(vis[y])chkmin(low[x],dfn[y]); } if(!f && child==1)cut[x]=0; }

边双（边双连通分量）：
概念：在求出所有的割边以后，把所有的割边删除，原图变成多个连通块。桥不属于任何一个边双连通分支，其余的边和每个顶点都属于且只属于一个边双连通分支。
原理：与点双同理，在求割边的过程中就能把每条边双连通分支求出，也是通过栈，不过此时自然是存边了，而不是点，之后栈的弹出边界与点双也是同理的，这里就不再赘述。
模板（code）：

void tarjan(int x,int fa){ dfn[x]=low[x]=++tim; LREP(x){ int y=E[i].y; if(E[i].flag||dfn[y]>=dfn[x])continue; E[i].flag=E[i^1].flag=1; stk[++top]=i; if(!dfn[y]){ tarjan(y,x); low[x]=min(low[x],low[y]); if(low[y]>dfn[x]){ tot++; do{ int k=stk[top]; if(mark[E[k].y]!=tot){ em[++cnt]=make_pair(tot,E[k].y); mark[E[k].y]=tot; } if(mark[E[k^1].y]!=tot){ em[++cnt]=make_pair(tot,E[k^1].y); mark[E[k^1].y]=tot; } Id[k>>1]=tot; }while(i!=stk[top--]); } } else low[x]=min(low[x],dfn[y]); } }

总结：

tarjan是一个非常使用且易记忆的算法，将一张有环图转换为DAG或一棵树后，
也就变成了一个十分常规的问题了，然后就可以再运用合理的数据结构或算法将其迎刃而解！