前言

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

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

浅谈 Tarjan

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

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

~~真心够短~~

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

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

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

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

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

前置芝士

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

DFS 树

顾名思义， $D F S$ 树即在 $D F S$ 过程中形成的树

就像这张图

e6VBpq.png

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

eyXI61.jpg

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

DFS 序

同理， $D F S$ 序即 $D F S$ 经过点的顺序。

还是刚才的图

e6VBpq.png

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

割点 & 割边の定义

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

别急，我们这就介绍

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

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

还是用这张图

e6VBpq.png

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

Tarjan 求割边

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

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

暴力删边

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

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

生成树删边

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

答案是肯定的。

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

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

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

Tarjan

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

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

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

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

在写代码时，我们开一个名为 $d f n$ 的数组记录 $D F S$ 序，再开一个名为 $l o w$ 的数组用于表示在 DFS 树的 x 的子树中，非树边往上指最小的 DFS 序。

之后直接模拟即可

Code

cpp

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$ ，如果它是割点，那么满足 $l o w [v] < d f n [u]$ ;

剩下的直接照抄即可

Code

cpp

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:

cpp

#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;
}