Tarjan求割点和桥

时间：2021-12-13 02:36:27

by szTom

前置知识

  1. 邻接表存储及遍历图
  2. tarjan求强连通分量

割点

割点的定义

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。

也就是说，就是有个点维持着连通分量的继续，去掉那个点，这个连通分量就无法在维持下去，分成好几个连通分量。

比如说，下图中

Tarjan求割点和桥

蓝色的点就是割点。

tarjan求割点

前向边

首先，先了解什么是前向边：

将这个无向图按树排列，从子节点到其祖先的边为前向边。

Tarjan求割点和桥

即为 \(low[x] < dfn[x]\) 时，有到x的前向边。

因为，low的定义是:

\[low[x]=
min\{dfn[y]\ |\ (x,y) \in E\
y\not = father[x] \}
$$即从$x$所能到达的点中$dfn[x]$最小的点。
### 方案

可以得出，设$y$是$x$的任意儿子，满足$$dfn[x] \leq low[y]$$的点$x$就是割点。
同时，当$x$为根节点且$x$的儿子数量多于$1$时，$x$是割点。

### 原理
如果一个点不是根节点，那么当它$dfn[x] \leq low[y]$时，没有关于$x$的前向边。这时删除点$x$的话，$x$的儿子节点就无法到达$x$的祖先了，故$x$是割点。
如果$x$是根节点，那么当它的儿子数量多于$1$时，删除$x$，其儿子节点无法互相到达，故$x$是割点。

## 代码实现
下面是[P3388 【模板】割点（割顶）](https://www.luogu.org/problem/P3388)的代码。
其中用`bool iscut[20005];`来记录割点。
```cpp
vector<int> G[20005];
int dfn[20005], low[20005];
int n, m;
int sum, root;
bool iscut[20005];

void tarjan(int x) {
int flag = 0;
dfn[x] = low[x] = ++sum;
for (unsigned i = 0; i < G[x].size(); ++i) {
int y = G[x][i];
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[y], low[x]);
if (low[y] >= dfn[x]) {
++flag;
if (x != root || flag > 1) iscut[x] = 1;
}
} else {
low[x] = min(low[x], dfn[y]);
}
}
}

int main() {
int x, y;
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}

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

int ans = 0;
for (int i = 1; i <= n; ++i) {
if (iscut[i]) ++ans;
}

cout << ans << endl;

for (int i = 1; i <= n; ++i) {
if (iscut[i]) cout << i << " ";
}
cout << endl;
return 0;
}
```

# 桥
## 定义
> 假设有连通图$G=\{V,E\}$，$e$是其中一条边（即$e \in E$），如果$G-e$是不连通的，则边$e$是图$G$的一条割边（桥）。

比如说，下图中，
![M5Wqqs.png-割边示例图](https://s2.ax1x.com/2019/11/21/M5Wqqs.png)
红色箭头指向的就是割边。

## tarjan求割边
和割点差不多，当存在边$(x,y) \in E$时，满足：$$dfn[x] < low[y]$$时，边$(x,y)$是一条割边。

## 代码实现
下面代码实现了求割边，其中，当`isbridge[x]`为真时，$(father[x],x)$为一条割边。
```cpp
int low[MAXN], dfn[MAXN], iscut[MAXN], dfs_clock;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];

void tarjan(int u, int fa) {
father[u] = fa;
low[u] = dfn[u] = ++dfs_clock;
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if(!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u]) {
isbridge[v]=true;
++cnt_bridge;
}
} else if(dfn[v] < dfn[u] && v != fa) {
low[u] = min(low[u], dfn[v]);
}
}
}
```

# 关于前向星（链式邻接表）
## 前向星的定义
> 一种数据结构，以储存边的方式来存储图。其优势有方便标记某一条边。

## 为什么要提前向星
本文中已经避免使用前向星，但网上绝大部分博客都使用提前向星。
下面不是前向星的教程（请自行百度），但可以帮助理解前向星。

## 理解前向星

1.遍历边
```cpp
for (int i = head[x]; i; i = nxt[u]) {
int y = to[i], w = weight[i];
//code
}
```
相当于：
```cpp
for (unsigned i = 0; i < G[x].size(); ++i) {
int y = G[x][i].x, w = G[x][i].w;
// code
}
```

2.相反边
`i`和`i ^ 1`互为反向边的编号。

邻接表要处理这种查询，可以新加一个变量记录：
```cpp
struct node {
int x, w; //original codes
int partner;
};
```

在建边时，加上：
```cpp
int x, y, w;
for (int i = 1; i <= m; ++i) {
cin >> x >> y >> w;
G[x].push_back((node) {y, w, G[y].size()});
G[y].push_back((node) {x, w, G[x].size() - 1});
}
```

需要时，`G[x][i]`的反向边是`G[G[x][i].x][G[x][i].partner]`

## 效率问题
容易看出，前向星的空间效率的常数比邻接表大。时间复杂度上理论相等，但因为`vector`的常数大，时间常数比较大。

# tarjan的复杂度
和模板没有区别，时间是$O(n+m)$，空间$O(n+m)$(要存图)

# 关于割点与桥的其他问题

## 定理？猜想？
可能会发现，割点与桥有如下性质:
> (1) 两个割点之间的边是割边。
> (2) 割边连接的点是有割点。

（1）这在很多情况上是正确无误的，但有反例，如：

![MTulBq.png](https://s2.ax1x.com/2019/11/22/MTulBq.png)

（2）除了两点一边的情况，是正确的。
证明嘛：~~略~~

# 练习题
## [P3388 【模板】割点（割顶）](https://www.luogu.org/problem/P3388)
模板题，割点。

## [POJ2117 Electricity](https://vjudge.net/problem/POJ-2117)
割点。

## [HDU4738 Caocao's Bridges](https://vjudge.net/problem/HDU-4738)
割边，不需要记录割边，tarjan时直接记录答案。
像这样：
```cpp
low[u] = min(low[u],low[v]);
if (low[v] > dfn[u]) {
ans = min(ans, G[v][i].w);
}
```

## [HDU2460 Network](https://vjudge.net/problem/HDU-2460)
割边 + LCA（暴力可以）

## [POJ1523 SPF](https://vjudge.net/problem/POJ-1523)
割点 + dfs。

@2019-11-21 广州市第二中学科技城校区\]

相关文章