0%

图的连通性总结

关于图的连通性.

强连通分量

有向图的一个极大强连通子图称为强连通分量.

强连通指图中的每一对点可以互相到达.

一般使用 Tarjan 算法求强连通分量.

用来在有向图上缩点, 然后拓扑序上 DP 或者做其他的事情.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void tarjan(int x) {
low[x] = dfn[x] = ++cnt;
s[++top] = x;
inq[x] = true;
for (auto to : g[x]) {
if (!dfn[to]) {
tarjan(to);
low[x] = std::min(low[x], low[to]);
} else if (inq[to]) {
low[x] = std::min(low[x], dfn[to]);
}
}
if (dfn[x] == low[x]) {
++sc;
while (s[top] != x) {
scc[s[top]] = sc;
inq[s[top]] = false;
--top;
}
scc[s[top]] = sc;
inq[s[top]] = false;
--top;
}
}

割点

删去这个点后无向图不再连通的点称为割点.

一般使用 Tarjan 算法求割点.

割点可以作为特殊的状态存储在图中.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void tarjan(int x, int p) {
low[x] = dfn[x] = ++cnt;
int s = 0;
for (auto i : g[x]) {
if (!dfn[i]) {
tarjan(i, x);
low[x] = std::min(low[x], low[i]);
if (x != p && low[i] >= dfn[x]) cut[x] = true;
if (x == p) ++s;
}
low[x] = std::min(low[x], dfn[i]);
}
if (x == p && s >= 2) cut[x] = true;
}

割边 (桥)

删去这条边后无向图不再连通的点称为割边.

一般使用 Tarjan 算法求割边.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void tarjan(int x, int p) {
dfn[x] = low[x] = ++cnt;
bool flag = false;
for (auto i : g[x]) {
if (!dfn[i]) {
tarjan(i, x);
low[x] = std::min(low[x], low[i]);
if (low[i] > dfn[x]) e[++tot] = (Edge){std::min(x, i), std::max(x, i)};
} else {
if (i == p && (!flag)) flag = true;
else low[x] = std::min(low[x], dfn[i]);
}
}
}

双连通分量

无向图的一个极大双连通子图称为双连通分量.

双连通指图中的每一对点在删除一条边或一个点后仍能互相到达 (边双连通或点双连通).

代码 (点双连通)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void tarjan(int x, int p) {
low[x] = dfn[x] = ++cnt;
sta[++top] = x;
if (x == p && (!g[x].size())) {
bcc[++bccCnt].push_back(x);
return ;
}
for (auto i : g[x]) {
if (!dfn[i]) {
tarjan(i, x);
low[x] = std::min(low[x], low[i]);
if (low[i] >= dfn[x]) {
++bccCnt;
while (sta[top] != x) {
bcc[bccCnt].push_back(sta[top]);
--top;
}
bcc[bccCnt].push_back(x);
}
}
low[x] = std::min(low[x], dfn[i]);
}
}

边双连通几乎跟强连通相同.