浅谈 OI 中的连通性相关算法
阅读方式：博客园（强烈推荐）
\S 1\quad 前言
本文旨在深入探讨图论中的强连通分量和双连通分量的求解方法及其理论基础，深入剖析 Tarjan 算法的本质。本文仅讨论求解连通分量的算法而不讨论缩点等引申问题。DFS 和 BFS 作为图论研究中的核心工具，将在本文中频繁涉及。因此，读者在阅读本文之前，应具备对 DFS 算法及其相关性质的扎实理解。
在强连通分量部分，本文将详细介绍经典的 Tarjan 算法，并探讨相对小众但具有独特价值的 Kosaraju 算法。在双连通分量部分，同样讲解 Tarjan 算法，并进一步阐述如何运用 Kosaraju 算法求解边双连通分量。尽管该方法在 OI 界中较少提及，但其算法实现的复杂度并不高于 Tarjan 算法，具有一定的应用价值。
Tarjan 算法在 OI 中已成为解决连通性问题的主流算法，其广泛的应用性和高效性备受青睐。然而，Kosaraju 算法亦具有重要的学习意义。在特定问题场景下，Kosaraju 算法的实现过程更为简洁，能够为问题求解提供更为高效的途径。
在 OI 中，不管是强连通分量，还是双连通分量，通常均是为了缩点（将一个分量缩成一个点），从而使得图变得更有性质。强连通分量缩点后变成 DAG，双连通分量缩点后变成树。在 DAG / 树上做，显然会容易许多。
\S 2\quad DFS 生成树
Tarjan 算法的关键便是 DFS 生成树，其内的大部分性质能够帮助我们有效地解决连通性问题，故让我们下来了解 DFS 生成树。DFS 生成树指在对有向图 / 无向图遍历的过程中所生成出的树，接下来将分别对有向图和无向图描述 DFS 生成树。
\S 2.1\quad 有向图的 DFS 生成树
有向图的 DFS 生成树共存在
- 树边（
\texttt{tree edge} ）：当 DFS 到u 点，向下搜索到还未被访问过的点v 时，便形成了一条树边(u,v) 。通过树边，构建出原图的一棵生成树。示意图中以黑色边表示。 - 反祖边（
\texttt{back edge} ）：在生成树中，u 点指向祖先节点v 的边。示意图中以蓝色边表示。 - 前向边（
\texttt{foward edge} ）：在生成树中，u 点指向u 点子树中节点v 的边。示意图中以红色边表示。 - 横叉边（
\texttt{cross edge} ）：在生成树中，u 点指向与点u 不存在祖先关系的节点v 的边。示意图中以绿色边表示。
【性质】 图
【习题】
- 如何通过 DFS 生成树判定有向图是否存在环？要求：时间复杂度为
O(n+m) 。 - [HT-043-Rainbow] 美愿时代的恨意
\S 2.2\quad 无向图的 DFS 生成树
无向图的 DFS 生成树共存在
- 树边（
\texttt{tree edge} ）：当 DFS 到u 点，向下搜索到还未被访问过的点v 时，便形成了一条树边(u,v) 。通过树边，构建出原图的一棵生成树。示意图中以黑色边表示。 - 后向边（
\texttt{back edge} ）：在生成树中，u 点连接祖先节点（非父亲节点）v 的边。示意图中以红蓝绿边表示。
【思考】 为什么在无向图中没有横叉边呢？
【解答】 假设存在横叉边
【习题】 如何通过 DFS 生成树判定无向图是否存在环？要求：时间复杂度为
\S 3\quad 强连通分量
【定义】
- 强连通：有向图
G 强连通是指G 中任意两个结点连通。 - 强连通分量（Strongly Connected Components，SCC）：极大的强连通子图。
\S 3.1\quad Tarjan 算法
考虑 DFS 生成树与强连通分量之间的联系，对于一个强连通分量，其在 DFS 生成树上必然是一棵子树，而这棵子树的根记作
依此设计算法，若能够求解出每个节点能够到达的深度最浅（或时间戳最小）的祖先节点，那么当且仅当这个节点是节点
可能略微难懂，举例说明：
如图橘色、红色、粉色、蓝色圈出的区域分别为
不难发现，
于是，接下来的问题便是如何快速找到每个节点能够到达的深度最浅（或时间戳最小）的祖先节点，为此定义
注意到，在
而
每当计算出 DFS(u) 结束的时候），判断
\text{Talk is cheap, show me the code.}
void tarjan(int u) {
dfn[u] = low[u] = ++ tot;
stk[ ++ top] = u, in_stk[u] = true;
for (auto v : g[u])
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stk[v])
low[u] = min(low[u], low[v]);
if (dfn[u] == low[u]) {
int w;
do {
w = stk[top -- ];
in_stk[w] = false;
/*
根据不同的题目，维护不同的信息。
*/
} while (w != u);
}
}\S 3.2\quad Kosaraju 算法
原图的汇是反图的源。
Kosaraju 的思想与 Tarjan 算法截然不同，Kosaraju 算法并没有用到 DFS 生成树，只是简单的 DFS 就解决了复杂的 SCC 问题。所以，笔者认为 Kosaraju 算法是非常优美的！
如
原图的汇是反图的源，这其实是反图上拓扑排序的过程，如果能得到反图的拓扑序，则按照该拓扑序在原图上不断 DFS，每次经过的点便是一个 SCC，注意不能遍历到之前 SCC 的点。于是，我们只需要得到反图的拓扑序即可，而 DFS 离开的顺序刚好是倒着的拓扑序，所以只需要在反图上跑一遍 DFS 并将离开的点的顺序记录出，并反着在原图上依此跑 DFS 即可。
如图，上来从
【习题】 如果先在原图跑出拓扑序，再在反图上跑对吗？如果对，说明理由；否则，给出反例。
\text{Talk is cheap, show me the code.}
void dfs1(int u) {
vis[u] = 1;
for (auto v : rg[u])
if (!vis[v]) dfs1(v);
ord[ ++ tot] = u;
}
void dfs2(int u) {
vis[u] = 1;
for (auto v : g[u])
if (!vis[v]) dfs2(v);
}
int main() {
// 读入，g 为原图，rg 为反图。
for (int i = 1; i <= n; i ++)
if (!vis[i]) dfs1(i);
memset(vis, 0, sizeof vis);
for (int i = n; i >= 1; i --)
if (!vis[ord[i]]) {
dfs2(ord[i]);
/*
根据不同题目维护不同信息
*/
}
}\S 4\quad 双连通分量
【定义】
- 边双连通：对于两个点
u 和v ，如果无论删去哪条边都不能使得它们不连通，就说u 和v 边双连通。 - 点双联通：对于两个点
u 和v ，如果无论删去哪个点都不能使得它们不连通，就说u 和v 点双连通。 - 边双连通分量：对于一个无向图中的 极大 边双连通的子图，我们称这个子图为一个 边双连通分量。
- 点双连通分量：对于一个无向图中的 极大 点双连通的子图，我们称这个子图为一个 点双连通分量。
双连通分量的 Tarjan 算法与强连通分量原理是一样的，所以大家可以先尝试自行思考，再往下阅读。
\S 4.1\quad 边双连通分量
边双连通分量和强连通分量是相通的。
\S 4.1.1\quad Tarjan 算法
与强连通分量类似，还是维护
接下来的部分均与强连通分量一致，有一个注意点是由于是无向边，一条树边
故，在写边双连通分量的时候，推荐使用链式前向星建图，这样容易维护父亲节点的边，因为每条边都有自己的编号。
\text{Talk is cheap, show me the code.}
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ tot;
stk[ ++ top] = u;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (i == fa) continue;
if (!dfn[v]) {
tarjan(v, i ^ 1);
low[u] = min(low[u], low[v]);
} else low[u] = min(low[u], low[v]);
}
if (low[u] == dfn[u]) {
int w;
do {
w = stk[top -- ];
/*
根据不同的题目，维护不同的信息。
*/
} while (w != u);
}
}\S 4.2\quad Kosaraju 算法
边双连通分量亦可 Kosaraju！
还记着，开头语说的边双连通分量和强连通分量是相通的？这是因为在通过 DFS 给无向图定向（树边向下，后向边向上）后，变成有向图，则每个强连通分量便是原来的边双连通分量！是不是很神奇？
实际上，原理是这样的。给无向图通过 DFS 定向后，原来每个环，现在仍然是有向环，而边双连通分量实际上就是由若干环拼接在一起的，而现在变成了若干个有向环拼接在一起，仍然是一个强连通分量（我相信没有人喜欢看枯燥无味的证明的，所以这里就不放，其实是不会证）。举个例子：
左图为边双连通图，右图为 DFS 定向后的图，蓝色虚线边为后向边，黑色边为树边。不难发现，这样定向后，最终是强连通图。
于是，考虑如何实现定向操作，笔者想到的实现方式是用深度实现，如果边
综上，使用链式前向星建图，第一次 DFS 的过程中标记哪些边使用了，第二次 DFS 在反图上跑一遍 DFS 即可。
实际上，这里只是将边双连通分量的求解转化为强连通分量的求解，并不是真正意义上的边双连通分量 Kosaraju。只是由于 Kosaraju 本身有一个 DFS 是在预处理，而定向可以同时进行，所以显得比较般配。但实际上，如果你先定向，然后再跑 Tarjan，只要不嫌麻烦，也没问题。
\text{Talk is cheap, show me the code.}
void dfs1(int u, int fa) {
vis[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (dep[v] <= dep[u] && fa != i) st[i] = 1;
if (!vis[v]) {
dep[v] = dep[u] + 1;
dfs1(v, i ^ 1);
}
}
ord[ ++ tot] = u;
}
void dfs2(int u) {
vis[u] = 1;
for (int i = h[u]; ~i; i = ne[i])
if (!vis[e[i]] && !st[i]) dfs2(e[i]);
}
int main() {
for (int i = 1; i <= n; i ++)
if (!vis[i]) dfs1(i, -1);
memset(vis, 0, sizeof vis);
for (int i = n; i >= 1; i --)
if (!vis[ord[i]]) {
dfs2(ord[i]);
/*
根据不同的题目，维护不同的信息。
*/
}
}\S 4.2\quad 点双连通分量（Tarjan 算法）
点双连通分量会比较反常，前文所述的连通分量都是互不相交地划分了所有点，而割点却可能出现在多个点双连通分量中。考虑如何求解割点，当知道点
如何判断点
那如何求点双连通分量呢？只需要当
\text{Talk is cheap, show me the code.}
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ tot;
stk[ ++ top] = u;
bool single = true;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
single = false;
if (i == fa) continue;
if (!dfn[v]) {
tarjan(v, i ^ 1);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
int w;
do {
w = stk[top -- ];
/*
根据不同的题目，维护不同的信息。
*/
} while (w != v);
// 注意：u 也在分量中
}
} else low[u] = min(low[u], dfn[v]);
}
if (single) res.push_back({u});
}\S 5\quad 结语
至此，我们讨论完了 OI 中的强联通分量和双连通分量的算法，讲述了 Tarjan 算法究竟是在干什么？为什么要这么干？以及 Kosaraju 算法和边双连通分量的 Kosaraju 算法（本质上是将边双转变为强连通分量）。
如果您认为文章哪里存在问题或理解不当，欢迎指出，感谢您的阅读。