不写博客会变懒，这是真的

原本好几天前就把Tarjan补完了，但是当时太懒，所以，现在变的更懒了，于是，我要回来把前几天落下的补回来了。

第一次接触Tarjan是在学lca时，Tarjan给了一种离线的做法，但那感觉只是用了Tarjan的思想，而且仅仅是在树上进行的。其实Tarjan是可以处理图上的问题的，主要体现在求割点和割边。

Tarjan有两个重要的数组，dfn表示dfs序，dfn[x]表示点x被第几个遍历到，low[x]表示点x能不通过回溯到达的最小的祖先。



Tarjan求割边

一条边是割边的充要条件是low[y]>dfn[x]。

我也不太清楚是为什么 可以感性认知一下，点y不通过回溯能到达的点在x点后边，也就是说除了x，y之间的边，y无法通过其他的边到达x，所以要是没有这条边，y后面的点将不和x连通，所以这条边是割边。

牛客小白月赛12 I

int head[N],ver[N*6],Next[N*6],tot=0;
void add(int x,int y){
    ver[++tot]=y;
    Next[tot]=head[x],head[x]=tot;
}
int dfn[N],low[N],cnt=0;
int ans=0;
void tarjan(int x,int fa){
    dfn[x]=low[x]=++cnt;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        if(y==fa)continue;
        if(!dfn[y]){
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x])ans++;
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    tarjan(1,0);
    printf("%d\n",m-ans);
}


Tarjan求割点

对于根节点来说，如果他有两个以上的儿子，他是割点。

对于非根节点来说，如果low[y]>=dfn[x]，他是割点。

感性认知同上。

Luogu P3388

int head[N],ver[N*6],Next[N*6],tot=0;
void add(int x,int y){
    ver[++tot]=y;
    Next[tot]=head[x],head[x]=tot;
}
int dfn[N],low[N],cnt=0;
int v[N];
void tarjan(int x,int fa){
    dfn[x]=low[x]=++cnt;
    int cnt=0;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        if(y==fa)continue;
        if(!dfn[y]){
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]&&x!=fa)v[x]=1;
            if(x==fa)cnt++;
        }
        else low[x]=min(low[x],dfn[y]);
    }
    if(fa==x&&cnt>=2)v[x]=1;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i,i);   ///保证仅根节点的fa==x
    }
    int ans=0;
    for(int i=1;i<=n;i++)if(v[i])ans++;
    printf("%d\n",ans);
    for(int i=1;i<=n;i++){
        if(v[i])printf("%d ",i);
    }
}


总结

通过上面的梳理可以得到一些结论

  1. 割点的数量一定大于等于割边的数量
  2. 存在割边就一定存在割点，存在割点不一定存在割边