tmd，前两天 cls 讲 SCC, 只讲了 Kosaraju，这是对 Tarjan 算法的极大的不尊重。
Robert E. Tarjan（罗伯特·塔扬，1948~），生于美国加州波莫纳，计算机科学家。
Tarjan 发明了很多算法和数据结构。不少他发明的算法都以他的名字命名，以至于有时会让人混淆几种不同的算法。比如求各种连通分量的 Tarjan 算法，求 LCA（Lowest Common Ancestor，最近公共祖先）的 Tarjan 算法。并查集、Splay、Toptree 也是 Tarjan 发明的。
我们这里要介绍的是在有向图中求连通分量的 Tarjan 算法。 —— OI-Wiki.org
首先，我们知道，对图进行 ，可以生成一棵树。
其中，有四种边：
- 树边（tree edge），树上的边。
- 横叉边（cross edge），指向其他子树的边（绿边）。
- 返祖边（back edge），指向父亲或祖先的边（蓝边）。
- 前向边（forward edge），指向子孙的边（红边）。
结论 1：对于任意的 ，若 是其所在强连通分量的第一个访问的节点，那么以 为根的子树一定包含了该强连通分量。
反证法：设 在 所在强连通分量，以 为根的子树不包含 。那么 必然在 之前访问过，不然 就处于 的子树中。此时与 是其所在强连通分量的第一个访问的节点矛盾。
现在我们来讲 Tarjan 求强连通分量的过程。
首先，我们有一个栈。
定义 为 的 DFS 序， 为以 为根的子树中横叉边或返祖边连接的 最小的在栈中节点的 。
我们按照 Dfs 对图进行以下操作： 维护每个结点的 与 ，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。对于每一个搜索到的 ，若存在单项边 ，考虑三种情况：
- 未被访问：搜索 ，维护 的 和 。
- 已被访问，在栈中： 是祖先，更新 。
- 已被访问，不在栈中： 所在的 SCC 处理完毕，忽略。
在回溯的过程中，判定 是否成立，如果成立，则栈中 u 及其上方的结点构成一个 SCC。因为此时必然有边从子树到 。
代码：
//摘自 OI-wiki
int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc; // 结点 i 所在 SCC 的编号
int sz[N]; // 强连通 i 的大小
void tarjan(int u) {
low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
for (int i = h[u]; i; i = e[i].nex) {
const int &v = e[i].t;
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
++sc;
while (s[tp] != u) {
scc[s[tp]] = sc;
sz[sc]++;
in_stack[s[tp]] = 0;
--tp;
}
scc[s[tp]] = sc;
sz[sc]++;
in_stack[s[tp]] = 0;
--tp;
}
}
时间复杂度 。实际上，由于只需要一次 Dfs 且 常数小，因此 Tarjan 算法的效率由于 Kosaraju 算法。
啊？Lca？不能写树剖吗？
Tarjan 求边双连通分量
我相信你知道这是什么意思。
首先，由于是无向图，所以没有横叉边。
搜索树上构成环当且仅当出现返祖边，即在无向图中该分量内不会出现桥，容易发现的是搜索树最终可以被划分为类似环-桥-环的结构，与边双联通分量的定义实际上是相符的。
因此，对于每一个 ，扩展到的 只有两种情况：子树与返祖/前向边，此时找到的强连通分量就是双联通分量。
void tarjan(int u, int f) {//f 记录从哪条边来，处理重边
low[u] = dfn[u] = ++idx;
st.push(u);
for(auto [v, x] : g[u])
if(x != f)
if(!dfn[v])tarjan(v, x), low[u] = min(low[u], low[v]);
else low[u] = min(low[u], dfn[v]);
if(low[u] == dfn[u]) {
++ top;
while(1) {
int v = st.top();
st.pop();
dcc[v] = top;
sz[top] ++;
ans[top].push_back(v);
if(v == u)break;
}
}
}
点双以后再写。
共 1 条回复
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊