# 有关图的连通性的Tarjan算法

## 割点与桥

#### 追溯值(low)

，它的追溯值要满足三个条件：

1)是 $$x$$

2)是通过一条不在搜索树上的边能回到 $$x$$

3)满足以上条件的最小值。

，考虑 $$x$$

.

$$low[x]=min(low[x],low[y])$$

$$(x,y)$$

$$low[x]=min(low[x],dfn[y])$$

void tarjan(int x, int intree) {
dfn[x] = low[x] = ++ cnt;
for (int i = Link[x]; i; i = e[i].next) {
int y = e[i].to;
if (!tarjan[y]) {
tarjan(y, i);
low[x] = min(low[x], low[y]);
}
else if (i != (intree ^ 1)) low[x] = min(low[x], dfn[y]);
}
}
//以下内容在main函数中：
tot = 1;
for (int i = 1; i <= n; ++ i) if (!dfn[i]) tarjan(i);

；以及异或(^)的优先级没有!=高，所以要在 $$intree^1$$

#### 割边的判定法则

$$y$$
$$x$$

，即在 $$x$$

$$x$$

HLOJ的模板题

#include<bits/stdc++.h>
using namespace std;
const int N = 100009, M = 300009;
int n, m, Link[N], tot = 1, dfn[N], low[N], cnt;
struct edge{int next, to, bridge;} e[M << 1];
void tarjan(int x, int intree) {
dfn[x] = low[x] = ++ cnt;
for (int i = Link[x]; i; i = e[i].next) {
int y = e[i].to;
if (!dfn[y]) {
tarjan(y, i);
low[x] = min(low[x], low[y]);
if (low[y] > dfn[x]) e[i].bridge = e[i ^ 1].bridge = 1;
}
else if (i != (intree ^ 1)) low[x] = min(low[x], dfn[y]);
}
}
inline bool cmp(answer x, answer y) {return x.x == y.x ? x.y < y.y : x.x < y.x;}
int main() {
freopen("danger.in", "r", stdin);
freopen("danger.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++ i) {
int x, y;
scanf("%d%d", &x, &y);
}
for (int i = 1; i <= n; ++ i) if (!dfn[i]) tarjan(i, 0);
cnt = 0;
for (int i = 2; i < tot; i += 2) if (e[i].bridge) ans[++ cnt].x = min(e[i ^ 1].to, e[i].to), ans[cnt].y = max(e[i ^ 1].to, e[i].to);
sort(ans + 1, ans + cnt + 1, cmp);
for (int i = 1; i <= cnt; ++ i) printf("%d %d\n", ans[i].x, ans[i].y);
return 0;
}

$$1$$

### 两道例题

#### 题意

$$(n<=100000,m<=500000)$$

#### 题解

1) $$x$$

2) $$x$$

3) $$x$$

, $$size[y]$$
, $$n-1-\sum size[y]$$
.

$$\sum size[y]*(n-size[y])+(n-1)+(\sum size[y])*(n-1-\sum size[y])$$