题解：P8435 【模板】点双连通分量

· · 题解

如果你感觉 Tarjan 算法太难理解了，你可以尝试树上差分。

这是一篇树上差分的题解。若想学习 Tarjan 算法请自行跳过。

感谢 @__TLE__ 提供的参考代码。此代码帮助我理解了树上差分。虽然我讲的做法和其代码逻辑不同，但还是感谢大佬出手相助。

先来介绍几个概念：

割点：无向图中，删除之后会使原来的连通块不连通的点。
点双连通分量：无向图中，极大的没有割点的子图。（也就是说，一直加点，加到加不动任何一个点）

注意：与边双连通分量不同，一个点可能属于多个点双连通分量，而一条边只能属于一个点双连通分量。

思路分析

我们现在要求无向图每个点双连通分量中的点。

我们先假设所有点构成一棵树。这个时候点双连通分量有 n-1 个，每一条边带着它连接的两个点成为一个独立的点双连通分量。

然后我们加入非树边。一条非树边会把一些树边合并在一起。如下图所示（蓝色的非树边将三条黑色的树边合并成了一个点双连通分量。此时，四个黑点全都在同一个点双连通分量中）。

这非常好！我们现在需要干的就是合并这些边。

直接暴力合并是不对的，因为一条非树边可能合并 O(n) 条树边。

这个时候我们可以使用树上差分。在第一条边的权值加一，最后一条边的权值减一。

我们定义一条边的最终权值为它连接的较深的节点的子树内的边的差分值的和，也就是把差分前缀和回来的值。

这样，如果一条边被合并它上面的边合并了，那么它最终权值一定不为 0。由差分的性质可以很快得到这个结论。

解法1

那么，现在我们就有了一个解法：

  1. 先求出差分数组。
  2. 统计每条边的最终权值。
  3. 如果最终权值不为 0：使用并查集合并这条边和上方的一条边。

时间复杂度为 O(n\alpha(n)+m)。

这不对呀，人家 Tarjan 都是 O(n+m)。能不能再给力一点？

我们换个角度思考，如果最终权值为 0,那么这一条边连接的深度较浅的点为割点，就是把两个点双连通分量分开的点。

解法2

那么现在，我们又有了一种解法：

  1. 先求出差分数组。
  2. 统计每条边的最终权值。
  3. 如果最终权值为 0：以较深的点为根的子树+较浅的点组成一个点双连通分量。然后把以较深的点为根的子树拆下来，因为它们不会属于上面的其他点双连通分量了。而较浅的点可能属于更多连通分量。

具体实现方式

复杂度分析

很显然，时间复杂度为 O(n+m)，空间复杂度为 O(n+m)。

对比 Tarjan：实际用时略优于 Tarjan。

具体地，Record Tarjan 7.26s，Record adj_diff(差分) 6.89s。

代码实现

:::info[here]

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,head[500010],idk,dep[500010],cf[4000010],idbcc;
struct node{
    int to,next,flag;
}e[4000010];
void adde(int u,int v){
    e[++idk]={v,head[u]};head[u]=idk;
}
int res[500010];
void dfs(int u,int fa){
    dep[u]=dep[fa]+1; 
    for(int i = head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa)continue;
        if(!dep[v])res[u]=i,e[i].flag=1,dfs(v,u);
        else if(dep[v]<dep[u])cf[res[v]]++,cf[res[fa]]--;
    }
}
vector<int> ans[500010];stack<int> stk;
void dfs2(int u,int fa){
    stk.push(u);
    for(int i = head[u];i;i=e[i].next)
        if(e[i].flag){
            res[u]=i;dfs2(e[i].to,u);
            cf[res[fa]]+=cf[i];
            if(cf[i]==0){
                idbcc++;
                while(stk.top()!=e[i].to){
                    ans[idbcc].push_back(stk.top());
                    stk.pop();
                }
                ans[idbcc].push_back(e[i].to);stk.pop();
                ans[idbcc].push_back(u);
                if(fa==0)fa=n+1;
            }
        }
    if(fa==0)ans[++idbcc].push_back(u);
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i = 1;i<=m;i++){
        int u,v;cin>>u>>v;
        adde(u,v);adde(v,u);
    } 
    for(int i = 1;i<=n;i++)if(!dep[i])dfs(i,0),dfs2(i,0);
    cout<<idbcc<<"\n";
    for(int i = 1;i<=idbcc;i++){
        cout<<ans[i].size()<<" ";
        for(int v:ans[i])cout<<v<<" ";
        cout<<"\n";
    }
}

:::

后记

在这之前，似乎树上差分一直都是跑 3 遍 dfs，包括我获得的 __TLE__ 大佬的参考代码。代码很长，常数也被 Tarjan 吊打。但是我这个是 2 遍 dfs，常数可以和 Tarjan 平起平坐的那种。

如果有任何问题，欢迎私信询问或在评论区留言！