割边
无向边 $(x,y)$ 是桥, 当且仅当搜索树上存在x的一个子结点y, 满足:
$$dfn_x < low_y$$
根据定义, $dfn_x < low_y$ 说明从 $subtree(y)$ 出发, 在不经过 $(x,y)$ 的前提下, 无法到达或比更早访问的顶点.
以P1656 炸铁路为例，核心部分为:
1
2
3
4
5
6
7
8
9
| if(!dfn[v]){
tarjan(v,x);
low[x]=min(low[x],low[v]);
if(low[v]>dfn[x]){
ve.push_back(make_pair(x,v));
}
}else{
low[x]=min(low[x],dfn[v]);
}
|
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
const int N=152,M=5003;
int head[N],nxt[M],to[M],num=0;
void add(int a,int b){
num++;
to[num]=b;
nxt[num]=head[a];
head[a]=num;
}
int dfn[N],low[N],cnt=0;
vector<pair<int,int>>ve;
void tarjan(int x,int f){
dfn[x]=low[x]=++cnt;
for(int i=head[x];i;i=nxt[i]){
int v=to[i];
if(v==f) continue;
if(!dfn[v]){
tarjan(v,x);
low[x]=min(low[x],low[v]);
if(low[v]>dfn[x]){
ve.push_back(make_pair(x,v));
}
}else{
low[x]=min(low[x],dfn[v]);
}
}
}
int main() {
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i,0);
}
sort(ve.begin(),ve.end());
for(auto i:ve){
cout<<min(i.first,i.second)<<" "<<max(i.first,i.second)<<endl;
}
return 0;
}
|
割点
若x不是搜索树的根结点, 则x是割点当且仅当存在x的一个子结点y, 满足:
$$dfn_x \le low_y$$
特别地, 若x是搜索树的根结点, 则x是割点当前仅当x存在至少两个子结点 $y_1$ $y_2$ 满足上述条件.
以P3388 【模板】割点（割顶）为例，核心部分为:
1
2
3
4
5
6
7
8
9
10
| if(!dfn[v]){
tarjan(v,x);
low[x]=min(low[x],low[v]);
if(low[v]>=dfn[x]){
tot++;
if(tot>=2||f!=0)ve.insert(x);
}
}else{
low[x]=min(low[x],dfn[v]);
}
|
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
using namespace std;
const int N=2e4+4,M=2e5+5;
int head[N],nxt[M],to[M],num=0;
void add(int a,int b){
num++;
to[num]=b;
nxt[num]=head[a];
head[a]=num;
}
int dfn[N],low[N],cnt=0;
set<int>ve;
void tarjan(int x,int f){
dfn[x]=low[x]=++cnt;
int tot=0;
for(int i=head[x];i;i=nxt[i]){
int v=to[i];
if(v==f) continue;
if(!dfn[v]){
tarjan(v,x);
low[x]=min(low[x],low[v]);
if(low[v]>=dfn[x]){
tot++;
if(tot>=2||f!=0)ve.insert(x);
}
}else{
low[x]=min(low[x],dfn[v]);
}
}
}
int main() {
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i,0);
}
cout<<ve.size()<<endl;
for(auto i:ve){
cout<<i<<" ";
}
return 0;
}
|
边双连通分量
求出无向图中所有的桥, 把桥删除后, 无向图会分为若干个连通块, 每一个连通块就是一个边双连通分量.
先求出所有的桥, 然后再进行DFS(不经过桥), 划分出连通块.
1
2
3
4
5
6
7
8
| void fb(int u) {
bl[u] = dcc;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (bl[v] || br[i]) continue;
fb(v);
}
}
|
1
2
3
4
5
6
7
|
for (int i = 1; i <= n; i++) {
if (!bl[i]) {
dcc++;
fb(i);
}
}
|
边双连通分量缩点
把每个边双连通分量看作一个顶点, 把桥 $(x,y)$ 看作连接编号为bl[x]和bl[y]的边双连通分量对应顶点的无向边, 那么将会产生一棵树(如果原图不连通，则产生森林).