前言

在昨晚(2019/8/3)模拟赛爆炸后，作者没脸在$C$班混下去了……

于是，作者便滚回了$D$，开始了被吊打的生活……

浅谈Tarjan

在介绍Tarjan算法之前，我们先来看一下百度百科的解释：

一种由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。 ——《百度百科》

~~真心够短~~

还是来看下更加通俗易懂的解释吧

Tarjan算法是由美国计算机学家Robert Tarjan提出的一系列算法，并不是一种算法。

在OI中，我们经常会用到Tarjan算法求割点，割边以及强连通分量。

同时，Tarjan算法还可以用来进行缩点，以简便我们的运算。

在本篇博客中，我们主要介绍用Tarjan求割点，割边。~~至于强连通分量什么的……就当我没带眼镜听不见好了o(´^｀)o~~

前置芝士

在介绍Tarjan求割点，割边之前，我们先来了解一些芝士

DFS树

顾名思义，$DFS$树即在$DFS$过程中形成的树

就像这张图

如果以$0$为起始点进行$DFS$，它的$DFS$树是这样的(画法不唯一)

仔细看一下上图，不难看出一颗DFS树不存在重复节点，也不存在跨子树的边

DFS序

同理，$DFS$序即$DFS$经过点的顺序。

还是刚才的图

如果以$0$为起始点进行$DFS$，它的$DFS$序为$0 , 1 , 2 , 3 , 4$

割点&割边の定义

既然我们要求的是割点与割边，那么它们的定义又是什么呐？

别急，我们这就介绍

割点就是把这个点在图中删去后，图中连通块的个数会增加的点

同理，割边就是把这条边在图中删去后，图中连通块个数会增加的边

还是用这张图

在这张图中，割点为点$0 , 3$。

Tarjan求割边

好，相信你现在~~已经完全理解了上面的内容~~，那么，我们现在开始介绍Tarjan求割边。

在想正解之前，我们先来想想暴力一点的做法

暴力删边

最暴力的想法应该就是每一次枚举一条边，将其删去，看是不是将原有的连通块拆分成多个连通块。

时间复杂度$O(n^2)$~~妥妥的TLE~~

生成树删边

对于刚刚的做法，我们有什么可以优化的吗？

答案是肯定的。

我们可以先寻找任意一颗生成树，然后仅判断生成树上的边是不是割边

正确性也很显然：因为生成树已经连接了所有的节点（原来就不连通的节点除外）。所以我们只要判断是不是有另一条边能绕过它即可

时间复杂度$O(n\times m)$，在数据较大时还是会超时。

Tarjan

仔细观察，我们不难得出结论：环上的边绝对不是割边，即不是割边的边都在某个环上

既然如此，我们就可以~~大胆猜想~~：不在任何一个环上的边为割边

所以我们先跑一遍$DFS$，求出$DFS$树，然后我们把图中的非树边（即不在$DFS$树上的边）加入$DFS$树中，看哪一条边被覆盖了。

那些没有被覆盖的边，即为割边。

在写代码时，我们开一个名为$dfn$的数组记录$DFS$序，再开一个名为$low$的数组用于表示在DFS树的x的子树中，非树边往上指最小的DFS序。

之后直接模拟即可

Code

namespace Tarjan_Edge{
    #define N 500001
    int dfn[N];
    int low[N];
    int cnt;
    inline void Tarjan(int root , int pre){
        dfn[root] = low[root] = cnt ++;
        for(int i = end[root] ; i ; i = edge[i].last){
            int to = edge[i].to;
            if(!dfn[to]){
                Tarjan(to , root);
                low[root] = min(low[root] , low[to]);
                if(low[to] > dfn[root]){
                    cout << root << "->" << to << endl;
                }
            }
            else if(to != pre){
                low[root] = min(low[root] , dfn[to]);
            }
        }
    }
}

Tarjan求割点

首先，对于一个根节点，如果它DFS树中的子树数量大于等于2，则它一定为割点

那么对于一个非根节点呐？

对于非根节点，我们要满足有一条非树边指向其DFS树上的祖先，他才会是一个割点。也就是说对于一个节点$u$，如果它是割点，那么满足$low[v] < dfn[u]$;

剩下的直接照抄即可

Code

namespace Tarjan_point{
    #define N 500001
    int dfn[N];
    int low[N];
    bool cut[N];
    int cnt;
    void Tarjan(int x , int fa){
    
        dfn[x] = low[x] = ++ cnt;
        int child = 0;
        for(int i = end[x] ; i; i = edge[i].last){
            int to = edge[i].to;
            if(!dfn[to]){
                Tarjan(to , fa);
                low[x] = min(low[x] , low[to]);
                if(low[to] >= dfn[x] && x != fa){
                    cut[x] = true;
                }
                if(x == fa){
                    child ++;
                }  
            }
            low[x] = min(low[x] , dfn[to]);
        }
        if(child >= 2 && x == fa){
            cut[x] = true;
        }
    }
}

附件[割点模板]

代码描述：见luoguP3388

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<iomanip>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>

#define N 500001
#define end head

using namespace std;

struct Edge{
    int to;
    int last;
}edge[N];

int edge_number;
int end[N];

void add_edge(int from , int to){
    edge[++ edge_number].to = to;
    edge[edge_number].last = end[from];
    end[from] = edge_number;
}

namespace Tarjan_point{
    int dfn[N];
    int low[N];
    bool cut[N];
    int cnt;
    void Tarjan(int x , int fa){
    
        dfn[x] = low[x] = ++ cnt;
        int child = 0;
        for(int i = end[x] ; i; i = edge[i].last){
            int to = edge[i].to;
            if(!dfn[to]){
                Tarjan(to , fa);
                low[x] = min(low[x] , low[to]);
                if(low[to] >= dfn[x] && x != fa){
                    cut[x] = true;
                }
                if(x == fa){
                    child ++;
                }  
            }
            low[x] = min(low[x] , dfn[to]);
        }
        if(child >= 2 && x == fa){
            cut[x] = true;
        }
    }
}

using namespace Tarjan_point;

int n , m;
int a , b;
int ans;

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i ++){
        cin >> a >> b;
        add_edge(a , b);
        add_edge(b , a);
    }
    for(int i = 1; i <= n; i ++){
        if(dfn[i] == 0){
            Tarjan(i , i);
        }
    }
    for(int i = 1; i <= n; i ++){
        if(cut[i]){
            ans ++;
        }
    }
    cout << ans << "\n";
    for(int i = 1; i <= n; i ++){
        if(cut[i]){
            cout << i << " ";
        }
    }
    return 0;
}