Tarjan详解

发表于 | 更新于 | 分类于 | 阅读次数：

Tarjan是一个很伟大的人

Tarjan的主要核心变量是$dfn$数组和$low$数组。前者表示DFS到某个点的时间戳，后者表示它的节点中，不通过当前节点可以到达的点最小的时间戳。

注意，对于强连通分量的low定义，应该为栈中可回溯到的$dfn$最小值。

详见下图。

​ SCC

如果用“后者表示它的节点中，不通过当前节点可以到达的点最小的时间戳。”这个定义，对于有四个点的强联通分量，根节点的low会被另外一个强连通分量更改而无法统计。

所以要理解为“栈中可回溯到的$dfn$最小值”。

Tarjan的实现

Tarjan通过DFS实现

大致如此。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Tarjan(int NowNode)
{
    _clock++;
    dfn[NowNode] = low[NowNode] = _clock;
    for (int i = head[NowNode]; i; i = edge[i]._next)
    {
        int NextNode = edge[i].to;
        if (!dfn[NextNode])
        {
            Tarjan(NextNode, NowNode);
            low[NowNode] = min(low[NextNode], low[NowNode]);
        }
        else if(判断语句（强连通分量为vis[NextNode]，割点是NextNode!=father）)
        {
            low[NowNode] = min(low[NowNode], dfn[NextNode]);
        }
    }
}

注意强连通分量的vis[NowNode]的判断，意思是这个元素是不是在栈中，如果在，才能更新。

一定要注意什么时候$low[NowNode] = min(low[NowNode], dfn[NextNode]);$

什么时候$low[NowNode] = min(low[NextNode], low[NowNode]);$

##割点与割边

首先明确一点，当一个点所有的子节点不通过当前节点都无法到达当前节点上面的点时，当前节点是割点，即$dfn[NowNode]\le low[NowNode]$。

同理，如果对于一条边$(NowNode,NextNode)$有$dfn[NowNode] < low[NextNode]$时，此条边是割边。

强连通分量

开一个栈来维护现在在联通分量中的。

当所有回溯结束后，发现$dfn[NowNode]==low[NowNode]$，就把栈内的东西标记到一起。

缩点

先把所有的强连通分量找出来，然后枚举每一条边，如果两个端点不在同一个强连通分量中就给新图加边。

大概就是这些。实现一定要注意对$low$数组的更新时刻。