Tarjan 算法

前置知识

基本图论，dfs 序和搜索树，栈

引入

Tarjan 算法由 Robert Tarjan 提出，具有线性复杂度，是图论中非常实用且通用的一个算法。

针对无向图，可以用来求图中的桥（删去后两边变得不连通的边，也叫割边）、割点（删去后它连接的部分变得不连通的点）；

针对有向图还可以进行缩点，也就是把所有能互相连通的点（这个叫强连通分量） 缩成一个点，在让图变无环的同时保留了一些性质，便于计算。

图中标注了桥和割点。

图中标注了可以替换为一个点的强连通分量。

思想

用 dfn[u] 存储 dfs 序；
用 low[u] 存储 u 能访问到的所有节点中，dfs 序的最小值。

至于 u 能访问到的所有节点，是这样定义的：

搜索树上以 u 为根的子树
从这棵子树一步能到达的所有节点（不包含 u 的父亲）

这里的定义比较特殊，一定要看清、牢记。

如果仍然觉得 low[] 输入的定义难以理解，可以这样想：
low[] 默认等于自身的 dfs 序，而在遍历的过程中 dfs 序是持续增加的，所以 low[] 变小的唯一可能是遇到了之前遇到过的点。
遇到这些点，一定经过了搜索树之外的边（叫做回边），这些边非常重要，正是它们保证了删去某些边后图仍联通。（若没有回边，那么图就是一棵树，树的每一条边都是桥）
Tarjan 的精髓就是在 dfs “撞到南墙”后继续向外探索一步，从而找到回边。

实现

如果上面的思想清楚了，实现其实没有什么难度。

直接 dfs，按照要求记录 dfn[] 和 low[]，同时注意不越界、不死循环即可。

下面是 tarjan 的应用：

桥

对于边 (u,v)，若 dfn[u]<low[v]，则这条边是桥。

这个式子意思是从 v 不能再访问到 u 本身和比 u 还先遍历的节点，也就是不能通过 (u,v) 之外的其他路径访问 u。

割点

对于边 (u,v)，若 dfn[u]<=low[v]，则这条 u 是割点。

这个式子意思是从 v 不能再访问到比 u 还先遍历的节点，但是允许访问 u 本身，就是说访问范围限定在 u 的子树内。

注意，叶节点不是割点，但因为这里考虑的是边，在正常遍历过程中不会对叶节点进行判断。

特别地，如果搜索树的根有两个以上的子树，那么它也是割点。

缩点

适用于有向图，搜索过程是相同的，在搜索同时还要将当前节点加入栈中。回溯时如遇到 dfn[u]=low[u]，则把 u 和其后的节点都从栈中弹出，弹出的这些节点就是一个强连通分量。

代码

桥

void tarjan(int u,int fa){
    dfn[u]=low[u]=++df;
    for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v])bri[i]=bri[i^1]=true;
        }else if(i!=(fa^1)){
            low[u]=min(low[u],dfn[v]);
        }
    }
}

需要注意的是，如果图中有重边，那么必须用这里 fa^1 的实现来避免死循环，而不能直接记录父节点，不然程序会将重边也认定为桥。

同时要记住 ^ 运算 01、23、34 是一对，记录边要从 2 开始。

割点

void tarjan(int u,int fa,int rt){
    int son=0;
    dfn[u]=low[u]=++df;
    for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v,i,rt);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<=low[v]&&u!=rt)cut[u]=true;
            son++;
        }else if(i!=(fa^1)){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(son>=2&&u==rt)cut[rt]=true;
}

与桥的不同在于对根节点的特殊判断，以及加上了等号。