--主要摘自北京大学暑期课《ACM/ICPC竞赛训练》

在有向图G中,如果任意两个不同顶点相互可达,则称该有向图是强连通的;

有向图G的极大强连通子图称为G的强连通分支;

Tarjan算法:

做一遍DFS,

Dfn[ i ] 表示节点i 在DFS过程中的访问序号(也可以叫做开始时间)。

Low[ i ]表示从i 节点出发DFS过程中i 下方节点(可以说是开始时间大于dfn[ i ],且由i 可达的节点;也可以说是与i邻接的未删除的顶点)所能到达的最早的节点的开始时间

DFS过程中,碰到哪个节点,就将哪个节点入栈。栈中节 点只有在其所属的强连通分量已经全部求出时,才会出栈。

如果发现某节点u有边连到栈里的节点v,则更新u的low 值为min(low[u],dfn[v]) ,若low[u]被更新为dfn[v],则表明目前 发现u可达的最早的节点是v.

对于u的子节点v,从v出发进行的DFS结束回到u 时,使得 low[u] = min(low[u],low[v])。因为u可达v, 所以v可达的最早的节点,也是u可达的。

如果一个节点u,从其出发进行的DFS已经全部完 成并回到u,而且此时其low值等于dfn值,则说明 u可达的所有节点,都不能到达任何比u早的节点 --- 那么该节点u就是一个强连通分量在DFS搜索树 中的根。

此时,显然栈中u上方的节点,都是不能到达比u 早的节点的。将栈中节点弹出,一直弹到u(包括u), 弹出的节点就构成了一个强连通分量.

在DFS过程中会形成一棵搜索树,在搜索树上越先遍历到的节点,显然dfn的值就 越小。dfn值越小的节点,就称为越“早”。

模拟一发:

萌新学习图的强连通(Tarjan算法)笔记-LMLPHP

顶点

Dfn

low

强连通分量

a

1

1

a

b

2

2

b,a

c

3

3

c,b,a

e

4

4

e,c,b,a=>e的low[i]==dfn[i] 变成c,b,a

{e}

d

5

5=>2(会访问到b,low[d]=min(dfn[b],low[b])=dfn[b]=2),

然后会回溯到c(low[c]=low[d]=dfn[b]=2),最终b的low[b]=dfn[b],b即为根;

a

{e},

{d,c,b}

f

6

6

f,a

{e},

{d,c,b}

g

7

7=>1会访问到a,low[g]=min(dfn[a],low[g])=dfn[a]=1),

然后会回溯到f(low[f]=low[g]=dfn[a]=1),最终a的low[a]=dfn[a],a即为根;

{e},

{d,c,b}

{g,f,a}

本人瞎几把说些吧。。。

在一次DFS的回溯过程中,如果发现low[i]==dfn[i],那么当前顶点就是一个强连通分量的根。

因为如果不是强连通分量的根,那么一定属于另一个强连通分量(好像说了句废话),

而且他的根是当前顶点的祖宗,那么存在包含当前顶点的到其祖宗的回路,

可知最终该顶点v一定会在他的DFS过程中访问到他的祖宗,并且他的Low[v]会被修改成比dfn[v]更小的值,

应该就是其祖宗的dfn[root]值吧。祖宗先访问到,入栈,然后到了下面的子节点,子节点能访问到祖宗,然而他在栈里,

所以一直比较dfn[root],而最小的值只有是dfn[root]和low[root],所以最终root下面顶点low[i]都会等于dfn[root]。OK。

//链式前向星;
struct asd{
int to;
int next;
};
asd edge[N];
int tol,head[N]; int tp; //记录当前访问时间
int p; //栈容量
int dfn[N]; //表示节点i 在DFS过程中的访问序号(也可以叫做开始时间)。
int low[N]; //表示从i 节点出发DFS过程中i 下方节点所能到达的最早的节点的开始时间。
bool vis[N]; //标记是否在栈中 void tarjan(int u)
{
dfn[u]=low[u]=++tp; //初始化
stap[++p]=u; //入栈
vis[u]=1; //标记
for(int v=head[u];v!=-1;v=q[v].next)
{
int i=q[v].to;
if(!dfn[i]) //如果还未被访问
{
tarjan(i);
low[u]=min(low[u],low[i]);
}
else if(vis[i]) //已被访问,且在栈中
low[u]=min(low[u],dfn[i]);
}
if(dfn[u]==low[u]) //如果是根节点
{
int temp;
while(1)
{
temp=stap[p];
vis[temp]=0; //出栈标记;
p--;
if(temp==u) //将该强连通分量弹出栈
break;
}
}
}

05-11 21:50