Tarjan有关应用更新边的起点到底是用low还是dfn

· · 算法·理论

文章目的：

由于我在写 Tarjan 时常常不知道到底是用 low_{now}=\min(low_{now},dfn_{i}) 还是用 low_{now}=\min(low_{now},low_{i}) 来更新边的起点——因为我发现这两种写法有时都能过。所以在我认真研究了两种写法的区别后，写了这篇文章来解决这个问题。

先说结论：

在 OI WIKI 上，low 的定义是：

设以 $u$ 为根的子树为 $subtree_{u}$。$low_u$ 定义为以下结点的 $dfn$ 的最小值： - $subtree_{u}$ 中的结点； - 从 $subtree_{u}$ 通过一条不在搜索树上的边能到达的结点。

或者说：

从节点 u 出发，沿着 DFS 树向下走，再通过至多一条返祖边（或横叉边）向上跳，能够到达的仍在栈中的节点的最小 dfn 值。

所以使用 low_{now}=\min(low_{now},dfn_{i}) 更新返祖边起点是 Tarjan 标准写法。那么现在要讨论的就是为什么 low_{now}=\min(low_{now},dfn_{i}) 可行以及什么时候可以使用 low_{now}=\min(low_{now},low_{i})。

思想：

对于强联通分量、点双、边双等无论什么应用的树边、前向边、返祖边、横叉边、自环等等无论什么边，到底是用 low_{now}=\min(low_{now},dfn_{i}) 还是用 low_{now}=\min(low_{now},low_{i}) 来更新边的起点的 low，根本是看应用，也即这种更新方式符不符合应用想要达成的目的。所以我认为，不必拘泥于 low 的标准定义，只要能通过自己定义的 low 达到目的就可以了。（能 AC 的代码就是好代码）

下面详细讲述每种情况：

由于一般对 dfn 和 low 的争议出现在返祖边，所以这里着重讲返祖边有关内容，其余边解释稍少。
由于我只学了 Tarjan 求强连通分量、边双、点双，所以这里只讨论这三种应用。

用语解释：

正片开始：

最后贴一下本文基于的模板代码：

Tarjan 模板

#include<bits/stdc++.h>
using namespace std;
int dfn[10005],low[10005],tim;
//dfn:表示点i是全局第几个被访问到的节点,只记录第一次访问时的时间戳,一旦记录不再更改 
//low:从节点i向上能访问到的最后一个节点的dfn，当low[i]==dfn[i]时，说明i无法再向根方向访问到\
    比它更早进入栈的节点了,说明这个i就是SCC的根 
//以上两个变量初始都为0 
void Tarjan(int now){
    dfn[now]=low[now]=++tim;
    //进入一个全新的节点(dfs保证只会进入新结点),记录第一次访问时的时间戳 
    for(int i:l[now]){
        if(!dfn[i])Tarjan(i),low[now]=min(low[now],low[i]);
        else if(p[i])low[now]=min(low[now],dfn[i]);}} 
int main(){
    int n=read(),m=read(),x;
    while(m--)x=read(),l[x].push_back(read());
    for(int i=1;i<=n;++i)
        if(!dfn[i])Tarjan(i);

    return 0;}

强连通分量

int a[10005],dfn[10005],low[10005],bel[10005],tim,scc_cnt;
//bel:i属于哪个强连通分量 
//tim:全局时间戳,每进入一个全新的节点就+1,然后赋给这个节点 
//scc_cnt:分量编号 
//以上三个变量初始都为0 
bool p[10005];//i是否在栈里 
stack<int>st;
vector<int>l[10005];
void dfs(int now){
    dfn[now]=low[now]=++tim;
    for(int i:l[now]){
        if(!dfn[i])dfs(i);//从未访问过(树边) 
        if(p[i])low[now]=min(low[now],low[i]);}//访问过且在该SCC内(返祖边) 
//前向边对SCC不做贡献,忽略 
//访问过但不在该SCC内的为横叉边，横叉边单向，两端不互通，故不能更新low
//自环在Tarjan算法中忽略,存图的时候直接不存
    if(low[now]==dfn[now]){
        ++scc_cnt;//知道这一部分是一个强连通分量了 
        int x;
        do{
            x=st.top();
            st.pop();
            p[x]=0;
            bel[x]=scc_cnt;
        }while(x!=now);}}//把从栈顶一直到根(包括根自己)的全部节点都弹出来,这一堆节点就是一个完整的强连通分量

边双连通分量（e-dcc）

#include<bits/stdc++.h>
using namespace std;
vector<int>l[155];
int dfn[155],low[155],tim;
vector<pair<int,int> >ans;
void dfs(int now,int fa){//只需记录父节点就可避免重复经过之前走过的点 
    dfn[now]=low[now]=++tim;
    for(int i:l[now]){
        if(i==fa)continue;
        if(dfn[i]==0){
            dfs(i,now);
            if(low[i]>dfn[now])ans.push_back({min(i,now),max(i,now)});}
        low[now]=min(low[now],low[i]);}}
bool cmp(pair<int,int> a,pair<int,int> b){
    if(a.first!=b.first)return a.first<b.first;
    return a.second<b.second;}
int main(){
    int n=read(),m=read();
    for(int i=1;i<=m;++i){
        int a=read(),b=read();
        if(a==b)continue;
        l[a].push_back(b),l[b].push_back(a);}
    for(int i=1;i<=n;++i)
        if(dfn[i]==0)dfs(i,0);
    sort(ans.begin(),ans.end(),cmp);
    for(auto i:ans)out<<i.first<<' '<<i.second<<'\n';
    return 0;}

点双连通分量（v-dcc）

#include<bits/stdc++.h>
using namespace std;
int head[500005],to[4000005],nxt[4000005],tot=1,dfn[500005],low[500005],tim,cnt;
vector<int>ans[500005];
stack<int>st;
void add(int u,int v){
    to[++tot]=u;nxt[tot]=head[v];head[v]=tot;}
void dfs(int u,int id){
    dfn[u]=low[u]=++tim;
    for(int i=head[u];i;i=nxt[i]){
        if(i==(id^1))continue;
        int v=to[i];
        if(!dfn[v]){
            st.push(i);
            dfs(v,i);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                ++cnt;
                int x;
                do{
                    x=st.top();st.pop();
                    ans[cnt].push_back(to[x]);
                    ans[cnt].push_back(to[x^1]);
                }while(x!=i);
                sort(ans[cnt].begin(),ans[cnt].end());
                ans[cnt].erase(unique(ans[cnt].begin(),ans[cnt].end()),ans[cnt].end());}}
        else if(dfn[v]<dfn[u])st.push(i),low[u]=min(low[u],dfn[v]);}}
int main(){
    int n=read(),m=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        if(u==v)continue;
        add(u,v),add(v,u);}
    for(int i=1;i<=n;++i)if(!dfn[i])dfs(i,0);
    for(int i=1;i<=n;++i)if(head[i]==0)ans[++cnt].push_back(i);
    out<<cnt<<'\n';
    for(int i=1;i<=cnt;++i){
        out<<(int)ans[i].size()<<' ';
        for(int j:ans[i])out<<j<<' ';
        out<<'\n';}
    return 0;}