系列文章目录
前言
第一次写算法，讲得肯不透彻，有误还请指教awa
文章目录
一、回顾
先来回顾一下dfs的基本框架：
//存图方式：vector(g[N])
void dfs(int u){//u:当前节点
vis[u]=true;
for(int& v:g[u]){//访问u连到的每个节点
if(!vis[v]) dfs(v);
}
}
二、tarjan算法
请注意，这里讲的仅限于无向图，有向图的算法会稍有不同。
- 首先我们可以确定的是回边一定不是桥1。
- 那么就只需要判断树边了。
回顾割边的定义，删边后两端断开，那么就意味着一端的点永远无法通过一条路径回到另一端，在DFS-tree上就体现为下方的节点永远无法通过非树边回到上方的点。如果成立，即只能通过树边相连，那么这条树边就是桥了！（因为是树，每个节点以自己为终点只会有一个直系父亲）
tarjan算法定义了两个数组：depth[]和low[]，定义如下：
-
depth[i]：节点i在DFS-tree上的深度。 -
low[i]：在dfs-tree上，以节点i及其子孙为起点的回边回到的 最低 高度。
假设我们已经算出每个节点的depth(下简称dep)和low，如何判断割边呢？
（务必注意，dep和low越大意味着越晚被遍历）
分类讨论一下吧：(假设目前在处理tree2上u->v边)
-
l o w [ v ] < = d e p [ u ] low[v]<=dep[u] low[v]<=dep[u]：意味着v(下方点)能回到u(上)及u以上的点，此时拿掉u-v，仍有至少1条路径使v能回溯到上面，不会断开，故不是桥。
-
l o w [ v ] > d e p [ u ] low[v]>dep[u] low[v]>dep[u]：意味着v只能回到u以下，此时若拿掉u-v，u、v间回断开，故是桥。
(很久以前的笔记)
至此，我们已经明确割边的判断，最后一件事便是求low值 了:
- 未访问过的点（树边）：那么这是原节点的子孙，只需在dfs改点后将二者low取min(因为存在下方没有树边的情况此时不需更新low)
- 已访问的点（回边）：(边u->v)取low[u]=min(low[u],dep[v])，注意回边终点用dep而非low，因为low去的时候回到的最早，不能二次回边。
2.1、求割边并输出
//vector<> g存图
int d=0;//深度从0开始
void dfs(int u){
vis[u]=1;
dep[u]=low[u]=d++;
for(int i=0;i<g[u].size();++i){
int& v=g[u][i];
if(!vis[u]){//树边
dfs(v);
low[u]=min(low[u],low[v]);//更新 low[]值
//仅在是树边时判断
if(low[u]>dep[v]) printf("%d-%d\n",u,v);
}
else{//回边
low[u]=min(low[u],dep[v]);
}
}
}
2.2、求连通分量
//求图的连通分量
int st[N],tp=0;//栈
int cn;//分量数量
int d=0;
void dfs(int u){
vis[u]=1;
dep[u]=low[u]=d++;
st[tp++]=u;//入栈
for(int i=0;i<g[u].size();++i){
int& v=g[u][i];
if(!vis[u]){
dfs(v);
low[u]=min(low[u],low[v]);
if(low[u]>dep[v]){
printf("第%d个连通分量：",++cn);
int t;
do{
t=st[tp--];
printf("%d ",t);
}while(t!=u);
printf("\n");
}
}
else{
low[u]=min(low[u],dep[v]);
}
}
return;
}
#if 0
算法实现：若u->v是桥，则当前栈出到v(v出)。
#endif
顺带一提，边-2-连通图 指至少删掉2条边才不连通（即无桥）。
THANK YOU !