tarjan算法 割点与割边

tarjan算法中的一些要素

dfn[i]代表时间戳,是访问该节点的时间。

low[i]代表追溯值。是该节点以及它的子树通过非搜索树边能追溯的dfn值最小的祖先的dfn值。

割点

割点的概念就是:在一张无向图中,去掉某一个点,这个图将会分裂成多个连通子图。

我们知道一个点不是割点,当前仅当这个点在至少一个简单环上。
我们还可以知道,不在搜索树上的边一定是一个点连到它的祖先的。而不是连到兄弟子树上去的。(如果连到兄弟子树上去了,那么肯定会dfs到这条边使它成为搜索树边)

如果一个点有一个儿子,该儿子为根的子树的能追溯到的祖先的dfn值如果大于等于这个点的dfn值,那么说明它是割点。
但是它如果是搜索树的根的话,还需要这样的条件:满足上述条件的儿子及子树有两个及以上。

所以一个点x是割点的充分必要条件就是它若不是搜索树的根,那么它存在一个儿子满足$low[y]>=dfn[x]$;若他是搜索树的根,那么它存在至少存在两个儿子满足上述条件。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
namespace TARJAN{
int dfn[maxn],low[maxn],cnt=0,root=0;
bool cut[maxn];
void tarjan(int x){
dfn[x]=low[x]=++cnt;
int flag=0;
for(int i=head[x];i+1;i=a[i].next){
int y=a[i].y;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
flag++;
if(x!=root||flag>1)cut[x]=true;
}
}
else low[x]=min(low[x],dfn[y]);
}
}
}using namespace TARJAN;

for(int i=1;i<=n;i++)
if(!dfn[i])
root=i,tarjan(i);

割边

仿照割点的概念。
如果在一张连通无向图中,如果一条边去掉之后,这张图不再连通,那么这条边是割边。
仿照割边的判定。
首先,割边一定是搜索树上的边。
如果一条搜索树上的边,连接着两个结点xy,且x是y的父亲,且满足$low[y]>dfn[x]$,那么就是割边了

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
namespace TARJAN{
int dfn[maxn],low[maxn],cnt=0;
bool bridge[maxm<<1];
void tarjan(int x,int in_edge){
dfn[x]=low[x]=++cnt;
for(int i=head[x];i+1;i=a[i].next){
int y=a[i].y;
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(low[y]>dfn[x])
bridge[i]=bridge[i^1]=true;
}
else{
if(i!=(in_edge^1))
low[x]=min(low[x],dfn[y]);
}
}
}
}using namespace TARJAN;

for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i,-1);
文章目录
  1. 1. tarjan算法中的一些要素
  2. 2. 割点
    1. 2.1. code
  3. 3. 割边
    1. 3.1. code