0%

图连通性学习笔记

大部分题目和解法都来自于 PKU 的 lyd 老师,谢谢您!

$\large\text{I.I 一些定义}$

割点:在割掉这个点之后图不连通了,即分裂成 $2+$ 个子图,则称这个点是割点。

割点集合:所有割点构成的集合为割点集合。

:在割掉这条边之后图不连通了,则称这条边是割边。

割边集合:定义同割点集合。

点双连通图:不存在割点的图。注意这个定义还有另一种等价表达方式,即所有点对之间点不相交的路径都至少有 $2$ 条。因为如果只有一条,那割随便一个点肯定就不连通了。

边双连通图:同点双连通图。

无向图G的极大(点/边)双连通子图称为(点/边)双连通分量。注意满足极大性。

所以我们也可以利用这个性质,去缩点解决一些问题。

$\large\text{I.II Tarjan算法}$

引入一个经典算法,本质上是对 $dfs$ 树的一系列操作。

传统定义:定义 $dfn$ 和 $low$ ,表示节点 $u$ 是第几个被 $dfs$ 到的(后文称为时间戳),以及每个点通过不在搜索树上的边能够到达的时间戳节点最小是多少。

注意无向图上的 $dfs$ 树,非树边一定是返祖边,这可以反证来考虑,这里就不多说了。

如何去实现这样一个算法

对于每一条边 $(u, v)$ ,若搜索树上 $v$ 是 $u$ 的子节点(即未 $visit$ ),则拿 $low_v$ 更新 $low_u$ 。若 $(u, v)$ 不是搜索树上的边(即返祖边),则直接更新 $low_u = min(low_u, dfn_v)$。

注意初值是 $dfn_u = low_u = ++clock$。

如何利用这个算法求割点

对于任意一条出现在搜索树 $(u, v)$ 上的边,其中 $u$ 是 $v$ 的父亲,若 $low_v \geq dfn_u$ ,则 $u$ 是割点。

为什么?因为 $v$ 和 $v$ 的子树跨不过点 $u$,即如果要和所有点有路径,肯定要经过 $u$ 。

我们在 $dfs$ 的同时回溯,判断即可。

注意一个细节:如果让你把割点都找出来,需要特判一下根。因为树根并没有父亲,所以判断他是不是割点的依据是他是否有 $>1$ 个孩子。

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
#include <bits/stdc++.h>
#define rep(i, l, r) for (__typeof(l) i = (l); i <= (r); ++i)
#define per(i, r, l) for (__typeof(r) i = (r); i >= (l); --i)
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 20020;
int dfn[N], low[N], cut[N], cl, n, m;
vector <int> g[N];
void tarjan(int u, int pre) {
int ch = 0;
low[u] = dfn[u] = ++cl;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (!dfn[v]) {
tarjan(v, u);
++ch;
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u] && u != pre) cut[u] = 1;
}
else if (v != pre) low[u] = min(low[u], dfn[v]);
// 注意这个 else if 和 else 的作用是等价的,因为可以直接加一个low的定义“可以通过自己的父亲边”
}
if (ch >= 2 && u == pre) cut[u] = 1;
}
int main() {
scanf ("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int x, y;
scanf ("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= n; ++i)
if (!dfn[i]) tarjan(i, i);
cout << count(cut + 1, cut + n + 1, 1) << endl;
for (int i = 1; i <= n; ++i)
if (cut[i]) printf("%d ", i);
return 0;
}

求点双连通分量的办法

还是依靠上面的算法。如果 $low_v \geq dfn_u$ ,就说明 $v$ 和 $v$ 的子树和 $u$ 共同构成了一个点双连通分量,这种情况可以搞一个栈,然后一个个 $pop$ 即可。

注意,不要 $pop$ $u$,while 的终止条件是当前

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void tarjan(int u, int pre) {
low[u] = dfn[u] = ++cl;
st[++tp] = u;
if (u == pre && !g[u].size()) {
DCC[++cnt].push_back(u);
return;
}
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]) {
++cnt;
while (st[tp] != v) DCC[cnt].push_back(st[tp--]);
DCC[cnt].push_back(st[tp--]);
DCC[cnt].push_back(u);
}
}
else low[u] = min(low[u], dfn[v]);
}
} // 有些题目中需要特判孤立点

题目一:给定 $n$ 个骑士和 $m$ 对憎恨关系,任意两个有憎恨关系的不能挨着,每次圆桌会议可以 $pick $ 奇数个人围一圈,求有多少个人永远不可能参加某一次圆桌会议。$n\leq 1000$。

sol: 建补图,然后就转化为了没有憎恨关系的可以挨着。考虑如果这个人参加不了,那就意味着他不在任何一个奇环内。

又有一个引理:若一个双连通分量里有奇环,则分量里所有点肯定都在至少一个奇环里。

这个怎么证明?考虑随便挑两个奇环上的点 $u, v$,$u\to v$ 一定至少有两条奇偶性。所以对于外面的一个点 $p$ ,一定有一条 $p\to u\to v\to p$ 的环满足是奇环。

又因为一个无向图有奇环等价于他不是二分图,所以直接判断每个点双是不是二分图即可。

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
#define rep(i, l, r) for (__typeof(l) i = (l); i <= (r); ++i)
#define per(i, r, l) for (__typeof(r) i = (r); i >= (l); --i)
using namespace std;
typedef long long ll;
const int mod = 998244353;
int read() {
int f = 1, x = 0; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x;
}
int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = (ll)res * a % mod; a = (ll)a * a % mod; b >>= 1; } return res; }

const int N = 1000 + 5;
int n, m, hav[N][N], eras[N], st[N], tp, mark[N], color[N];
int low[N], dfn[N], cl, cnt;
vector <int> DCC[N], g[N];
void tarjan(int u, int pre) {
low[u] = dfn[u] = ++cl;
st[++tp] = u;
if (u == pre && !g[u].size()) {
DCC[++cnt].push_back(u);
return;
}
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]) {
++cnt;
while (st[tp] != v) DCC[cnt].push_back(st[tp--]);
DCC[cnt].push_back(st[tp--]);
DCC[cnt].push_back(u);
}
}
else low[u] = min(low[u], dfn[v]);
}
} // 有些题目中需要特判孤立点

void mar(int id) {
for (int i = 0; i < DCC[id].size(); ++i) mark[DCC[id][i]] = id;
}
bool dfs(int u, int col) {
color[u] = col;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (mark[v] != mark[u]) continue;
if (color[v] == -1) {
if (!dfs(v, 1 - col)) return 0;
}
if (color[u] == color[v]) return 0;
}
return 1;
}
int main() {
while (~scanf ("%d%d", &n, &m) && (n || m)) {
rep (i, 1, n) rep (j, 1, n) hav[i][j] = (i == j);
rep (i, 1, n) g[i].clear(), dfn[i] = low[i] = cl = mark[i] = 0;
rep (i, 1, n) eras[i] = 0;
while (cnt) DCC[cnt--].clear();
rep (i, 1, m) {
int u, v;
scanf ("%d%d", &u, &v);
hav[u][v] = hav[v][u] = 1;
}
rep (i, 1, n)
rep (j, i+1, n)
if (!hav[i][j]) g[i].push_back(j), g[j].push_back(i);
rep (i, 1, n) if (!dfn[i]) tarjan(i, i), --tp;
int ans = 0;
rep (i, 1, cnt) {
memset(color, -1, sizeof(color));
mar(i);
if (!dfs(DCC[i][0], 0)) {
for (auto e: DCC[i]) eras[e] |= 1;
}
}
rep (i, 1, n) ans += !eras[i];
printf("%d\n", ans);
}
return 0;
}

利用 Tarjan 算法求桥

还是同样的道理,唯一区别是把 $low_v \geq dfn_u$ 改成了 $low_v > dfn_u$ ,则称 $(u, v)$ 是桥。

具体代码实现有一点小区别,需要特判 $(u, v)$ 不在 $dfs$ 树上的时候才有 $dfn_v \to low_u$。

当然仔细思考后可以发现,如果 $low_u \geq dfn_u$,也可以说 $(f, u)$ 是桥。

板子不写了,到时候碰到题再写


Luogu P3469: 给一个无向图,求删除每个点后有多少个有序点对间的联通关系会受到破坏,n <= 100000.

解法:考虑只有割点才会破坏某些联通关系。这种情况下,

不妨观察一下这个图。你会发现,最后留下来的孤立的联通块一定满足 $low_v \geq dfn_u$。这样的话我们只需要加一个 $sz_v \times (n - sz_v)$ 的贡献。

这样我们已经把子树到别的的都算完了,还差到上面的贡献($(n - sum - 1) \times (sum + 1)$),以及中间那个点到别的点对答案的贡献($n - 1$)。

加上这些即可。

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 <bits/stdc++.h>
#define rep(i, l, r) for (__typeof(l) i = (l); i <= (r); ++i)
#define per(i, r, l) for (__typeof(r) i = (r); i >= (l); --i)
using namespace std;
typedef long long ll;
const int mod = 998244353;
int read() {
int f = 1, x = 0; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x;
}
int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = (ll)res * a % mod; a = (ll)a * a % mod; b >>= 1; } return res; }
const int N = 100010;
int n, m, dfn[N], low[N], cl, sz[N];
ll ans[N];
bool is_cut[N];
vector <int> g[N];
void tarjan(int u, int pre) {
dfn[u] = low[u] = ++cl;
sz[u] = 1;
int ch = 0;
ll sum = 0;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (!dfn[v]) { // 是树边
// cerr << u << " -> " << v << '\n';
tarjan(v, u);
low[u] = min(low[u], low[v]);
sz[u] += sz[v];
++ch;
if (low[v] >= dfn[u]) {
if (u != pre) is_cut[u] = 1;
ans[u] += 1ll * sz[v] * (n - sz[v]);
sum += sz[v];
}
} else low[u] = min(low[u], dfn[v]);
}
if (ch >= 2 && u == pre) is_cut[u] = 1;
if (is_cut[u]) {
ans[u] += 1ll * (n - sum - 1) * (sum + 1) + n - 1;
}
}
int main() {
n = read(), m = read();
rep (i, 1, m) {
int a = read(), b = read();
g[a].push_back(b);
g[b].push_back(a);
}
tarjan(1, 1);
rep (i, 1, n) {
if (!is_cut[i]) printf("%lld\n", 2 * (n - 1));
else printf("%lld\n", ans[i]);
}
return 0;
}

CF1276B Two Fairs

题意:给一个无向图,求有多少个点的路径必定经过 a 和 b, n <= 1e5.

碰到这种题先随便画个图:

然后你发现这可以用圆方树/细节割点讨论过掉,但是有更简单的办法。

我们发现必经过 $a, b$ 的路径都有一个特点,就是截取中间这条路径是唯一的。(废话)

我们从 $b$ dfs,看能不能尽可能不过 $a$ 的 $dfs$ 到所有点。注意这个时候如果有点还 $dfs$ 不到,那就是这个点到 $b$ 必定经过 $a$。

同理再从 $a$ dfs,再看能不能尽可能不过 $b$。如果有点 dfs 不到,就说明这个点到 $a$ 必定经过 $b$。

然后乘一下两部分未被 $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
#include <bits/stdc++.h>
#define rep(i, l, r) for (__typeof(l) i = (l); i <= (r); ++i)
#define per(i, r, l) for (__typeof(r) i = (r); i >= (l); --i)
using namespace std;
typedef long long ll;
const int mod = 998244353;
int read() {
int f = 1, x = 0; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x;
}
int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = (ll)res * a % mod; a = (ll)a * a % mod; b >>= 1; } return res; }


const int N = 200020;
int n, m, a, b, vis[N];
vector <int> g[N];
void dfs(int t) {
vis[t] = 1;
for (int i = 0; i < g[t].size(); ++i) {
int v = g[t][i];
if (!vis[v]) dfs(v);
}
}
void solve() {
n = read(), m = read(), a = read(), b = read();
rep (i, 1, n) g[i].clear();
rep (i, 1, m) {
int u = read(), v = read();
g[u].push_back(v);
g[v].push_back(u);
}
rep (i, 1, n) vis[i] = 0;
vis[a] = 1;
dfs(b);
ll forbid = count(vis + 1, vis + n + 1, 0);
rep (i, 1, n) vis[i] = 0;
vis[b] = 1;
dfs(a);
forbid *= count(vis + 1, vis + n + 1, 0);
printf("%lld\n", forbid);
}
int main() {
for (int T = read(); T; --T) solve();
return 0;
}

转载一下 mike 的题解:

我们来注意到必须经过 $a$ 和 $b$ 的路径他有一个特点,就是在删掉 $a$ 和 $b$ 后,起点和终点都不在同一个联通块里。

所以考虑容斥,拿所有点对个数减掉两次恰有一次在同一个联通块里的点对个数。

后面那个恰有一次就再容斥成 $\geq 1$ 次 $-$ $=2$ 次即可,拿一个 $map$ 记录就好了。

这做法听起来就正经多了。


强联通分量不讲了,实际用到的时候只用缩点,板子也很好背。


HAOI2006 受欢迎的牛:问有多少个点能被其他所有点到达。

缩点,然后变成了dag上的问题。

考虑一个强联通分量能被其他的到达,正是意味着其他的所有强联通分量都有出度。

所以,如果有一个以上的分量没有出度,那答案就是 $0$。否则,所有就是唯一一个出度为 $0$ 的联通分量的大小。

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
#include <bits/stdc++.h>
#define rep(i, l, r) for (__typeof(l) i = (l); i <= (r); ++i)
#define per(i, r, l) for (__typeof(r) i = (r); i >= (l); --i)
using namespace std;
typedef long long ll;
const int mod = 998244353;
int read() {
int f = 1, x = 0; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x;
}
int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = (ll)res * a % mod; a = (ll)a * a % mod; b >>= 1; } return res; }

const int N = 10010;
int n, m, ins[N], dfn[N], low[N], cl, cnt, bels[N], sz[N], deg[N];
vector <int> g[N];
stack <int> stk;
void tarjan(int u) {
dfn[u] = low[u] = ++cl;
ins[u] = 1;
stk.push(u);
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (ins[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
++cnt;
while (true) {
int t = stk.top();
stk.pop();
ins[t] = 0;
bels[t] = cnt;
++sz[cnt];
if (t == u) break;
}
}
}
int main() {
n = read(), m = read();
vector <pair <int, int> > edges;
rep (i, 1, m) {
int a = read(), b = read();
edges.push_back({a, b});
g[a].push_back(b);
}
rep (i, 1, n) if (!dfn[i]) tarjan(i);
for (auto e: edges) if (bels[e.first] != bels[e.second])
++deg[bels[e.first]];
if (count(deg + 1, deg + cnt + 1, 0) > 1) cout << 0 << endl;
else {
rep (i, 1, n) if (!deg[i]) return cout << sz[i] << endl, 0;
}
return 0;
}