Tarjan 算法处理 缩点、割点、割边

强连通分量SCC缩点

对有向图进行简化操作，将图中的强连通分量合并为一个节点

合并后的节点具有合并前所有节点的权值贡献且不会重复，对于边的处理当且仅当 SCC 内部有出入边时才映射

例：洛谷P3387 https://www.luogu.com.cn/problem/P3387

const int N=1e4+10;

vector<int> e[N];
vector<int> stk;
bool instk[N];
int dfn[N],low[N],idx;
int scc[N],nw[N],cnt;
vector<int> ne[N];
int dp[N];
int w[N];

void tarjan(int x){
    dfn=low=++idx;
    stk.push_back(x);
    instk=1;
    
    for (auto v:e){
        if (!dfn[v]){
            tarjan(v);
            low=min(low,low[v]);
        }else if (instk[v])
            low=min(low,dfn[v]);
    }
    
    if (low==dfn){
        int t;
        cnt++;
        do{
            t=stk.back();
            stk.pop_back();
            instk[t]=0;
            scc[t]=cnt;
            nw[cnt]+=w[t];//计算合并后权值
        }while (t!=x);
    }
}

void solve(){
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>w[i];
    for (int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
    }
    
    for (int i=1;i<=n;i++)
        if (!dfn[i]) tarjan(i);
        
    for (int i=1;i<=n;i++){
        for (auto v:e[i])
            if (scc[i]!=scc[v])
                ne[scc[i]].push_back(scc[v]);
        dp[i]=nw[i];
    }
    
    int ans=0;
    for (int i=cnt;i>=1;i--){
        for (auto v:ne[i])
            dp[v]=max(dp[v],dp[i]+nw[v]);
        ans=max(ans,dp[i]);
    }
    cout<<ans;
}

首先遍历这张图，Tarjan算法处理出所有的强连通分量：scc[N] ，同时，计算合并节点的总权值 nw[N]

然后对边进行映射：

for (int i=1;i<=n;i++)
    for (auto v:e[i])
        if (scc[i]!=scc[v])//当且仅当这条边不在SCC内才映射
            ne[scc[i]].push_back(scc[v]);

最后计算简化后的图上最大权值路径，因为我们对 SCC 编号是拓扑逆序的，所以最后逆向遍历这张图

采用类似 DP 的方式计算最大权值

int ans=0;
for (int i=cnt;i>=1;i--){
    for (auto v:ne[i])
        dp[v]=max(dp[v],dp[i]+nw[v]);//更新权值
    ans=max(ans,dp[i]);
}

割点

在一张无向图中，删去某个顶点后图中的极大连通分量数增加，那么该点为一个割点

判定法则：如果节点 $x$ 不是根节点，当且仅当搜索树上存在一个 $x$ 的子节点 $y$ 满足 ${\rm{low}}_y\ge {\rm{dfn}}_x$ 时 $x$ 为割点。如果 $x$ 是根节点，当且仅当搜索树上至少存在两个子节点 $y_1,y_2$ 满足 ${\rm{low}}_{y_{1,2}}\ge {\rm{dfn}}_x$ 时 $x$ 为割点

vector<int> e[N];
int dfn[N],low[N],idx;
int cut[N],root;

void tarjan(int x){
    dfn=low=++idx;
    int son=0;
    for (auto v:e){
        if (!dfn[v]){
            tarjan(v);
            low=min(low,low[v]);
            if (low[v]>=dfn){//判断是否为割点的必要条件
                son++;//x的子树+1
                if (x!=root||son>1)//判断根节点的情况
                    cut=1;
            }
        }else
            low=min(low,dfn[v]);//直接更新
    }
}

void solve(){
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i=1;i<=n;i++){
        if (!dfn[i]){
            root=i;//指定当前连通分量的根节点
            tarjan(i);
        } 
    }
    int sum=0;
    for (int i=1;i<=n;i++) sum+=cut[i];
    cout<<sum<<endl;
    for (int i=1;i<=n;i++)
        if (cut[i]) cout<<i<<' ';
}

特别的，在无向图中不存在横叉边，所以不用考虑 $v$ 是否在栈内（任何非树边都必然是后向边）因此可以直接用 ${\rm{dfn_v}}$ 更新 ${\rm{low}}_x$

割边（桥）

在一张无向图中，删去某条边后图中的极大连通分量数增加，那么该点为一个割边或桥

判定法则：当搜索树上存在 $x$ 的一个子节点 $y$ 满足 ${\rm{low}}_y>{\rm{dfn}}_x$ 时，这条边为割边

struct edge{int u,v;};
vector<edge> e;
vector<int> h[N];
int dfn[N],low[N],idx;
vector<edge> bri;

void tarjan(int x,int ine){
    dfn=low=++idx;
    for (auto ote:h){
        int v=e[ote].v;
        if (!dfn[v]){
            tarjan(v,ote);
            low=min(low,low[v]);
            if (low[v]>dfn)
                bri.push_back(e[ote]);
        }else if (ote!=(ine^1))
            low=min(low,dfn[v]);
    }
}


void solve(){
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e.push_back({u,v});
        h[u].push_back(e.size()-1);
        e.push_back({v,u});
        h[v].push_back(e.size()-1);
    }
    
    for (int i=1;i<=n;i++)
        if (!dfn[i]) tarjan(i,0);
    
    auto cmp=[](edge x,edge y){
        if (x.u!=y.u) return x.u<y.u;
        return x.v<y.v;
    };
    
    sort(bri.begin(),bri.end(),cmp);
    for (auto e:bri){
        if (e.u<e.v)
            cout<<e.u<<' '<<e.v<<endl;
        else
            cout<<e.v<<' '<<e.u<<endl;
    }
}

因为要处理边，所以不采用邻接点的方式存边，而是直接记录边集

struct edge{int u,v;};
vector<edge> e;

而且图是一张无向图，对边进行编号时我们按照连续奇偶序号编号

vector<int> h[N];//节点的出边
e.push_back({u,v});
h[u].push_back(e.size()-1);//按照边加入的顺序编号，从0开始
e.push_back({v,u});
h[v].push_back(e.size()-1);//反向存边

Tarjan算法实现时，通过 h[N] 记录的出边编号建立搜索树

for (auto ote:h){
    int v=e[ote].v;
    if (!dfn[v]){
        tarjan(v,ote);
        low=min(low,low[v]);
        if (low[v]>dfn)
            bri.push_back(e[ote]);
    }else if (ote!=(ine^1))
        low=min(low,dfn[v]);
}

因为对同一条边，正反编号时连续的奇偶，那么可以通过异或运算确定两条边是否为同一条无向边

else if (ote!=(ine^1)) //当这条出边ote边和入边ine不是同一条边时才更新