强连通分量(二)——tarjan
开这篇文章之前可以先看一下强连通分量(一)——kosaraju。个人认为kosaraju要更容易理解一些,但是要慢一些。一些概念性的东西在这篇博客中就不作说明了。
接下来我们直接进入主题:tarjan
tarjian的复杂度和kosaraju一样,都是O(n+m),但是kosaraju一般丑一些常数大一些,而且面临的爆栈风险也更大,因此tarjan算法要更常用一些(tarjan的效率比kosaraju高30%左右)。当然,我个人认为kodaraju可以为理解tarjan算法做一些铺垫,这个因人而异吧qwq。
tarjan算法是基于DFS的。我们首先建立一个栈。对于每个节点,我们记录两个值:dfn和low。其中,dfn表示该节点的搜索序号,而low表示此节点能到达的栈中dfn最小的节点。
对于每次搜索,我们首先将当前节点加入栈中,然后记录下当前节点的dfn,同时将low设置为dfn相等。接下来我们就开始便利该节点的子节点。。。对于没有被访问过的子节点,我们直接更新当前节点的low值为当前值和其子节点的low值的最小值。如果我们发现此节点有一个子节点被访问过且这个节点在栈中(即不属于任何强连通分量,因为所有节点只要被访问过且不在栈中,那么其必定属于了一个强连通分量),那么我么就更新这个节点的low为当前值和此子结点的low值的最小值。
回溯时,我们将每个节点的low更新为它的所有子节点的low值的最小值。这样,我们不难发现,如果当前节点的low值等于dfn值,那么它显然对于我们搜索的顺序上来说是强连通分量的顶点,因此我们将栈中的所有节点开始挨个弹出直到当前节点。我们弹出的所有节点就组成了一个强连通分量。
下面给出代码(说明:路径使用邻接表存储):
相关练习:BZOJ 1051 [HAOI2006]受欢迎的牛、BZOJ 2140 稳定婚姻
接下来我们直接进入主题:tarjan
tarjian的复杂度和kosaraju一样,都是O(n+m),但是kosaraju一般
tarjan算法是基于DFS的。我们首先建立一个栈。对于每个节点,我们记录两个值:dfn和low。其中,dfn表示该节点的搜索序号,而low表示此节点能到达的栈中dfn最小的节点。
对于每次搜索,我们首先将当前节点加入栈中,然后记录下当前节点的dfn,同时将low设置为dfn相等。接下来我们就开始便利该节点的子节点。。。对于没有被访问过的子节点,我们直接更新当前节点的low值为当前值和其子节点的low值的最小值。如果我们发现此节点有一个子节点被访问过且这个节点在栈中(即不属于任何强连通分量,因为所有节点只要被访问过且不在栈中,那么其必定属于了一个强连通分量),那么我么就更新这个节点的low为当前值和此子结点的low值的最小值。
回溯时,我们将每个节点的low更新为它的所有子节点的low值的最小值。这样,我们不难发现,如果当前节点的low值等于dfn值,那么它显然对于我们搜索的顺序上来说是强连通分量的顶点,因此我们将栈中的所有节点开始挨个弹出直到当前节点。我们弹出的所有节点就组成了一个强连通分量。
下面给出代码(说明:路径使用邻接表存储):
void tarjan(int k)
{
++sum;
dfn[k]=sum;
low[k]=sum;
st[++top]=k;//入栈
int d=head[k];
while(d!=0)
{
if(!dfn[a[d].v])//如果当前节点没有被搜过
{
tarjan(a[d].v);//向下搜
low[k]=min(low[k],low[a[d].v]);//更新low
}
else
if(!co[a[d].v])//如果当前节点被搜过且在栈中
low[k]=min(low[k],dfn[a[d].v]);//更新low
d=a[d].next;
}
if(dfn[k]==low[k])//如果当前节点是强连通分量的顶点
{
col++;
while(dfn[st[top]]!=low[st[top]])
{
num[col]++;
co[st[top]]=col;
top--;
}
co[st[top]]=col;
num[col]++;
top--;//从栈中弹出此强连通分量
}
return;
}
相关练习:BZOJ 1051 [HAOI2006]受欢迎的牛、BZOJ 2140 稳定婚姻
评论
发表评论