eyhLF0.jpg

前言

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

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


浅谈 Tarjan

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

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

真心够短

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

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

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

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

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


前置芝士

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

DFS 树

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

就像这张图

e6VBpq.png

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

eyXI61.jpg

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


DFS 序

同理,DFS 序即 DFS 经过点的顺序。

还是刚才的图

e6VBpq.png

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


割点 & 割边の定义

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

别急,我们这就介绍

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

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

还是用这张图

e6VBpq.png

在这张图中,割点为点 0,3


Tarjan 求割边

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

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


暴力删边

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

时间复杂度 O(n2) 妥妥的 TLE


生成树删边

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

答案是肯定的。

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

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

时间复杂度 O(n×m),在数据较大时还是会超时。


Tarjan

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

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

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

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

在写代码时,我们开一个名为 dfn 的数组记录 DFS 序,再开一个名为 low 的数组用于表示在 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,如果它是割点,那么满足 low[v]<dfn[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;
}

THE END