众所周知,
求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法,以及求最近公共祖先(LCA)的离线Tarjan算法,在此对Tarjan表示崇高的敬意。,
这里只对求割点进行代码剖析。
所以
上板子
void tarjan(int now){//now当前节点 int num1=0;//dfn为时间戳,low为时间戳最小的祖先 dfn[now]=low[now]=++num; vis[now]=true; for(int i=head[now];i;i=edge[i].nxt){//利用链式前向星依次访问临边 int to=edge[i].to; if(!vis[to]){ fa[to]=now;tarjan(to);//记录父亲,深搜 low[now]=min(low[to],low[now]);//更新low值 if(dfn[now]<=low[to])num1++;//儿子能到达祖先,不是割点 //反之,是割点 } else if(fa[now]!=to)low[now]=min(low[now],dfn[to]); // 也有更新low值的作用 } if(now==1&&num1>1)ans[++ans[0]]=now;//根节点要special judge,至少2个 if(now!=1&&num1)ans[++ans[0]]=now; // 记录割点 }其实很简单~~~~
感谢姓徐的撑船的人~~~~~