Tarjan

Tarjan算法是图论中非常常用的算法之一，能解决强连通分量，双连通分量，割点和桥，求最近公共祖先（LCA）等问题。

Tarjan 算法是基于深度优先搜索的算法，用于求解图的连通性问题。

割点

如果从图中删除节点 \(x\) 以及所有与 \(x\) 关联的边之后，图将被分成两个或两个以上的不相连的子图，那么称 \(x\) 为图的割点。

如3、5就是图的割点

桥/割边

如果从图中删除边 \(e\) 之后，图将分裂成两个不相连的子图，那么称 \(e\) 为图的桥/割边。

如图中边 \((3,5)\) 就是图的割边

实现

几个定义

强连通分量 :
对于一个分量，若任意两个点相通，则称为强连通分量。

树边 :
对于一个图的dfs树，它的树边便是此图的树边。

返祖边 :
对于一个图的dfs树，可以使得儿子节点返回到它的祖先的边为返祖边。

横插边 :
对于一个图的dfs树，可以使得一个节点到达另一个节点且它们互不是祖先的边为横插边。

连通

连通：无向图中，从任意点 \(i\) 可到达任一点 \(j\) 。
强连通：有向图中，从任意点 \(i\) 可到达任一点 \(j\)。
弱连通：把有向图看作无向图时，从任意点i可到达任一点 \(j\)。

强连通分量

整个图并不是强连通的，但是在某些局部区域符合强连通的要求，如下图，整张图不算是强连通，但局部还是能满足强连通条件的。

时间戳

时间戳是用来标记图中每个节点在进行dfs时被访问的顺序，可以理解成一个由小到大的序号（类似于dfs序）。

搜索树

在无向图中，以某一个节点 \(x\) 出发进行dfs，每一个节点只访问一次，所有被访问过的节点和边构成一棵树，称之为“无向连通图的搜索树”。

追溯值

追溯值用来表示从当前节点 \(x\) 能够访问到的所有节点中，时间戳最小的值。
能够访问到的节点其需要满足下面的条件之一：

以 \(x\) 为根的搜索树的所有节点。
通过一条非搜索树上的边，能够到达搜索树的所有节点。

代码

dfn:第 \(i\) 个节点的时间戳

low:第 \(i\) 个节点最多经过一条返祖边所能到达的最小时间戳

st:一个栈,用来储存当前还未确定但已经扩展过的点

bb:第 \(i\) 个节点他所在的强连通分量编号

void tarjan(int 当前点){
    这个点的low=dfn=时间戳;
    将这个点入栈;
    标记这个点入栈;
    for(这个点连接的所有边){
        if(目标点没有被访问过){
            tarjan(目标点);
            更新当前点的low; 
        }else if(目标点被访问过){
            更新当前点的low; 
        } 
    }
    if(当前点的low==dfn){
        将这个点及栈以上的点出栈，标记成一个强连通分量; 
        ans++; 
    } 
}