Tarjan求割点(洛谷3388)

用 tarjan 遍历整个图,如果某个点是割点,当且仅当以下两种情况

  1. 当前点是根节点,且当前节点出发独立的联通分量至少有两个
  2. 当前点不是根节点,且当前节点出发的独立分量能回溯到的最早的点在当前节点之后

转换过来就是下面两个条件

  1. u == root && child >= 2
  2. u != root && low[v] >= dfn[u]

其他与 tarjan 算法无异。

代码

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
56
57
58
59
60
61
62
63
64
65
66
67
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
using namespace std;

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 100010;
int n, m, u, v, pos, ans, dfn[maxn], low[maxn], cut[maxn];
int tot = 2, hed[maxn], nxt[maxn << 1], to[maxn << 1];

void add_edge(int u, int v) {
nxt[tot] = hed[u];
to[tot] = v;
hed[u] = tot++;
}

void tarjan(int u, int root) {
dfn[u] = low[u] = ++pos;
int child = 0;
for (int i = hed[u], v = to[i]; i; i = nxt[i], v = to[i]) {
if (!dfn[v]) {
tarjan(v, root);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u] && u != root)
cut[u] = 1;
child++;
} else {
low[u] = min(low[u], dfn[v]);
}
}
if (u == root && child >= 2)
cut[u] = 1;
}

int main() {

n = read(), m = read();
for (int i = 1; i <= m; i++) {
u = read(), v = read();
add_edge(u, v);
add_edge(v, u);
}

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

for (int i = 1; i <= n; i++)
ans += cut[i];

printf("%d\n", ans);
for (int i = 1; i <= n; i++)
if (cut[i])
printf("%d ", i);
puts("");

return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×