警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「题目汇总」Tarjan题目汇总

这里是一些Tarjan题目的汇总。

进度:ABCDEF

A, Caocao's Bridges, 桥

传送门:HDU4738YaliOJ

题意

曹操在长江上弄了一些点,点之间有桥。每座桥上有若干人守卫。现在刘备有一枚炸弹,问最少带多少人去炸桥可以使点之间不连通。如果不可能输出 \(-1\)

解法

\((u,v)\)\(u\) 在 dfs 树下为 \(v\) 的子节点) 为桥的充要条件是 \(low_v>dfn_u\),也就是 \(u\) 的子节点 \(v\) 无法到达 \(u\) 及其之上的点,那么如果切断 \((u,v)\) 那么图将不会联通。

这道题的坑点如下:

  • 如果已经不连通了输出 0

处理方式:记录 dfs 拓展出的节点数,如果发现不到 \(n\) 那么显然不连通,输出 \(0\) 即可。

(expand+1 == n) * ans

  • 如果没人守卫还是要输出 1

处理方式:如果 \(ans\)\(0\) 那么取 \(ans\)\(1\) 的 max 就好了。

(expand+1 == n) * max(1, ans)

最后加上对 \(ans=+\infty\) 的特判:ans == 0x3f3f3f3f ? -1 : (expand+1 == n) * max(1, ans)

  • 重边需要特殊处理。(因为 dfs 树的特殊性,只需考虑父节点——子节点的重边即可)

处理方式:如果父节点到子节点只连了一次边,那么不需要用父节点更新。否则把父节点当成子节点更新

代码

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
#include <bits/stdc++.h>
using namespace std;

struct edge {
int to, next, weight;
} e[2000006];

int dfn[1003], low[1003], head[1003], idx, cnt, ans, expand;

void addedge(int x, int y, int z) {
e[++cnt] = (edge){y, head[x], z}; head[x] = cnt;
e[++cnt] = (edge){x, head[y], z}; head[y] = cnt;
}

void dfs(int x, int par) {
dfn[x] = low[x] = ++idx;
int f = 0;
for (int i = head[x]; i; i = e[i].next) {
int nx = e[i].to;
if (!dfn[nx]) {
dfs(nx, x);
expand++;
low[x] = min(low[x], low[nx]);
if (low[nx] > dfn[x]) {
ans = min(ans, e[i].weight);
}
} else if (nx == par) {
if (f) low[x] = min(low[x], dfn[nx]);
f = 1;
} else low[x] = min(low[x], dfn[nx]);
}
}

int n, m, x, y, z;

int main() {
while (~scanf("%d%d", &n, &m) && (n || m)) {
memset(head, 0, sizeof head);
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(e, 0, sizeof e);
idx = cnt = expand = 0;
ans = 0x3f3f3f3f;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &x, &y, &z);
addedge(x, y, z);
}
dfs(1, -1);
printf("%d\n", ans == 0x3f3f3f3f ? -1 : (expand+1 == n) * max(1, ans));
}
}

Y三集

B, Railway, 点双+桥

传送门:HDU4738YaliOJ

C, Network, 边双

传送门:HDU2460YaliOJ

D, TWO NODES, 割点

传送门:HDU4587YaliOJ

题意

给你一张图,问你删掉两个点最多能有多少个连通块。\(n,m\le5000\)

解法

枚举其中一个删除的点,然后 Tarjan 求一遍割点。答案取 max。

未完待续……

代码

E, Warm up, 边双缩点

F, Important Sisters, 支配树