Tarjan 强连通分量

本篇是 Tarjan 主课；掌握 SCC 与缩点后，可到《强连通分量与缩点》第五节选学 2-SAT。

Tarjan 算法关注的是有向图的连通性分析与拓扑缩点（识别并提取图中的环状结构）。

Tarjan 算法依赖的是深度优先搜索树 (DFS Tree) 与时间戳回溯（通过记录节点的访问顺序和可达的最高祖先来判定环的边界）。

Tarjan 算法的核心思想是栈维护与状态隔离（暂存已经访问、但还没归入某个 SCC 的节点；确认一个完整分量后，再统一出栈）。

一、核心定义与问题背景

在无向图中，连通性是双向的。但在有向图中，存在边 $A \to B$ 并不意味着存在 $B \to A$。这导致有向图的连通性分析更为复杂。

• 强连通 (Strongly Connected)：在有向图中，如果节点 $u$ 和节点 $v$ 之间能够互相到达，则称 $u$ 和 $v$ 是强连通的。
• 强连通分量 (Strongly Connected Component, SCC)：有向图中的一个极大子图，在这个子图内的任意两个节点都能互相到达。单独的一个节点也被视为一个强连通分量。

算法应用背景（缩点）：

拓扑排序和按拓扑序转移的 DP，需要有向无环图 (DAG)。原图有环时，拓扑排序就排不完，我们得先把这些互相依赖的部分处理掉。

Tarjan 算法的通常目的是将每一个强连通分量“压缩”成一个单一的“超级节点”（即缩点）。缩点后的新图必然是一个 DAG，从而可以将问题转化为常规的 DAG 上动态规划问题。

通俗类比： “城市交通圈的合并”。

如果几个城市之间有单向高速公路形成了一个完整的闭环，车辆可以在这几个城市间无限循环穿梭。在进行宏观路径规划时，我们可以将这几个形成闭环的城市视为一个巨大的“都市圈”（超级节点），从而简化整个国家的交通网络。

二、核心原理与状态转移逻辑

Tarjan 算法本质上是对图进行了一次深度优先搜索（DFS）。在搜索过程中，维护以下三个核心状态：

1. 状态数组的严格数学定义

• dfn[u]（DFS Number / 时间戳）：表示节点 $u$ 在 DFS 过程中首次被访问的次序。该值一旦分配，永不改变。
• low[u]（追溯值）：从 $u$ 出发，沿 DFS 树向下走，再通过至多一条指向栈内节点的非树边，所能追溯到的最小时间戳。可以先记成：这一支还能联系到多早的、尚未出栈的节点？

2. 状态转移方程

在遍历节点 $u$ 的相邻节点 $v$ 时，存在以下三种情况：

1. 树边（$v$ 未被访问过）：

   此时 dfn[v] == 0，我们递归向下搜索 dfs(v)。回溯时，用子树的追溯值更新当前节点：

   $$low[u] = \min(low[u], low[v])$$

2. 返祖边/横叉边（$v$ 被访问过，且仍在栈中）：

   此时到达了一个尚未出栈的节点，用它的时间戳更新。它可能是祖先，也可能已经结束递归、但仍在等待分量归属；Tarjan 的栈不只是当前递归路径。

   $$low[u] = \min(low[u], dfn[v])$$

3. 废弃边（$v$ 被访问过，但已不在栈中）：

   说明 $v$ 属于一个已经处理完毕并输出的强连通分量，与当前节点所在的分量无关。直接忽略，不进行状态转移。

3. 强连通分量的识别与出栈

当节点 $u$ 的所有边都遍历完毕后，检查是否满足：

如果相等，说明这一支不能再联系到比 $u$ 更早的未出栈节点。于是 $u$ 就是当前强连通分量在 DFS 树中的最高点（根节点）。

此时，栈中位于 $u$ 之上的所有节点（包括 $u$ 自身），正好构成了一个完整的强连通分量。将它们依次弹出并打上相同的 SCC 编号。

三、标准求解算法与模板

易错点分析： 在判断已访问节点时，严格使用 else if(instk[v])。如果不判断目标节点是否仍在栈内，横叉边可能会将 low[u] 错误地更新为其他已经隔离的 SCC 的时间戳，导致算法逻辑完全崩溃。

下面的模板只求 scc 编号和 sz 大小，输出部分按具体题目补充。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 100005;
vector<int> node[N];

// 核心状态数组
int dfn[N];     // 时间戳
int low[N];     // 追溯值
int instk[N];   // 标记节点是否在栈中
int scc[N];     // 记录节点 u 所属的强连通分量编号
int sz[N];      // 记录第 i 个强连通分量包含的节点个数

int id = 0;     // 全局时间戳分配器
int sc = 0;     // 强连通分量计数器
stack<int> stk; // 保存已经访问、但尚未归入 SCC 的节点

void dfs(int u) {
    // 1. 初始化当前节点的状态并入栈
    dfn[u] = low[u] = ++id;
    stk.push(u);
    instk[u] = 1;

    // 2. 遍历相邻节点，进行状态转移
    for (int v : node[u]) {
        if (!dfn[v]) {
            // 情况 A：v 未被访问，产生树边，向下递归
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (instk[v]) {
            // 情况 B：v 已经被访问且在栈中，产生返祖边或有效的横叉边
            low[u] = min(low[u], dfn[v]);
        }
        // 若 v 已访问且不在栈中（instk[v] == 0），属于情况 C，直接忽略
    }

    // 3. 识别强连通分量根节点，执行出栈隔离
    if (dfn[u] == low[u]) {
        sc++; // 产生一个新的强连通分量
        int x = 0;
        do {
            x = stk.top();
            stk.pop();
            instk[x] = 0;    // 标记出栈
            scc[x] = sc;     // 染色：记录节点所属的 SCC 编号
            sz[sc]++;        // 统计该 SCC 的节点数量
        } while (x != u);    // 直到将根节点 u 自身也弹出
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        node[u].push_back(v);
    }
    
    // 图可能是不连通的，必须遍历每一个节点作为潜在的搜索起点
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            dfs(i);
        }
    }
    return 0;
}

四、例题

Tarjan 算法求出 SCC 后，最常规的操作是“缩点建新图”。

缩点方法：遍历原图的所有边 $u \to v$。如果 $scc[u] \neq scc[v]$，说明这条边连接了两个不同的强连通分量。在缩点后的新图中，我们建立一条从 $scc[u]$ 指向 $scc[v]$ 的单向边。新图必然是 DAG。

1. 💡 基础应用：出度/入度分析 (洛谷 P2341 受欢迎的牛)

• 问题背景：$N$ 头牛有单向的仰慕关系。仰慕关系具有传递性。求被所有牛都仰慕的牛的数量。

• 算法分析：

  用 Tarjan 把强连通分量缩成点。在新 DAG 中，若只有一个出度为 $0$ 的超级节点，那么从其他点沿出边走，最终都只能停在这里，因此所有点都能到达它。

  注意事项：如果缩点后的 DAG 中存在两个或以上出度为 $0$ 的节点，则不存在被所有人仰慕的牛。若只有一个出度为 $0$ 的超级节点，答案即为该超级节点内包含的原节点个数（sz 数组）。

2. 💡 进阶应用：缩点 + DAG 上的动态规划 (洛谷 P3387 【模板】缩点)

• 问题背景：给定一个有向图，每个节点有权值。求一条路径，使得路径经过的节点权值之和最大。经过多次的节点权值只计算一次。

• 算法分析：

  因为经过多次只计算一次，所以如果走进了一个环，我们一定可以把这个环里的所有节点都走一遍，获取它们的全部权值。

  1. 使用 Tarjan 算法求出所有的强连通分量。
  2. 统计每个 SCC 的总权值（即内部所有节点的权值和）。
  3. 执行缩点操作，建立一张全新的 DAG。
  4. 在 DAG 上运用拓扑排序，进行常规的动态规划求解最长路径即可：$dp[v] = \max(dp[v], dp[u] + weight[v])$。转移顺序可回看《拓扑排序与 DAG 动态规划》第三节。

  开始时令每个分量的 dp[u]=weight[u]，表示允许从它自己出发；按拓扑序转移后，答案取所有 dp[u] 的最大值。重边可以保留，只要邻接表存几次、入度就加几次，处理时也减几次，二者保持一致即可。

// 缩点建新图的核心代码片段（假设新建的图存入 new_node 数组，入度存入 in_degree）
for (int u = 1; u <= n; u++) {
    for (int v : node[u]) {
        if (scc[u] != scc[v]) {
            new_node[scc[u]].push_back(scc[v]);
            in_degree[scc[v]]++;
        }
    }
}

五、栈与出栈的对照手推：警惕无效横叉边

在状态转移时，遇到已经访问过的点 $v$，为什么一定要判断 instk[v]？我们来看一个一旦漏写就会致命的例子。

场景构造： 假设图中有 3 个节点，有向边为 $1 \to 2$、$1 \to 3$、$3 \to 2$。

手推模拟 DFS 过程：

1. 从 1 开始，走 $1 \to 2$。节点 2 进栈，dfn[2]=2, low[2]=2。
2. 节点 2 没有出边，发现 dfn[2] == low[2]。节点 2 作为一个完整的强连通分量出栈。此时 instk[2] = 0。
3. 回溯到 1，继续走另一条边 $1 \to 3$。节点 3 进栈，dfn[3]=3, low[3]=3。
4. 节点 3 有一条出边 $3 \to 2$。此时发现节点 2 已经被访问过了（它有 dfn）。

对照时刻：

• 如果错误地不加判断直接转移：low[3] = min(low[3], dfn[2])。此时 low[3] 会被错误地更新为 $\min(3, 2) = 2$。回溯到 3 结算时，dfn[3] != low[3]（即 $3\ne2$），算法会认为 3 不是强连通分量的根。3 会一直留到回溯到 1，与 1 一起弹出，错误地得到 SCC $\{1,3\}$。
• 正确的逻辑（判断 instk[2]）：因为节点 2 已经出栈（instk[2] == 0），说明它已经打包结算完毕，属于独立的“都市圈”。$3 \to 2$ 是一条废弃的横叉边，不能用它来更新 low[3]。节点 3 保持 low[3]=3，顺利出栈，自己单独成为一个强连通分量。

这就是栈的“隔离”魔法：它帮我们屏蔽了那些早就走投无路、已经被打包结算的分量，防止时间戳发生时空错乱。

六、缩点建图的实战细节：权值合并与重边效应

1. 为什么同一分量可以“合并权值”？

在类似洛谷 P3387（缩点求最大权值路径）的题中，有一个至关重要的条件：“经过多次的节点权值只计算一次”。 这个条件是我们能将 SCC 压缩成单个超级节点、并将其内部节点权值简单相加的物理前提。

因为强连通分量的特性是“内部任意两点互通”，一旦你踏入了这个分量中的任何一个点，你就可以在里面无限循环穿梭。配合上“重复经过不重复计算”的规则，这就变成了一个“自助餐区”：只要你进门了，你绝对有办法白嫖里面所有节点的权值，最后再随便挑一个有出边的节点离开。

如果没有这个条件（比如每次经过都要累加权值），那图中有环意味着权值可以无限大；如果是边权且规定“每条边只能走一次”（类似欧拉路径），那就不能简单缩点相加，因为你可能走不完分量里的所有边就必须出去了。

2. 缩点后的“重边”怎么处理？

很多同学在写缩点建图时会产生疑问：假设超级节点 A 中有两个原节点，都各有一条边指向超级节点 B 中的某个原节点。遍历原图边建新图时，A 到 B 就会建出两条一模一样的有向边（重边）。这需要用 if 或者 set 费力去重吗？

其实大部分情况下，完全不需要去重。

• 对 DP 的影响：在新 DAG 上跑最长路 dp[v] = max(dp[v], dp[u] + weight[v])。即使 $u$ 到 $v$ 有两条边，你只是把相同的转移方程多执行了一次，完全不会改变 max 的结果。
• 对入度的影响：建图时加了两条边，in_degree[B] 就多加了 2。但在拓扑排序时，当 A 出队，我们会遍历 A 的所有出边，把 in_degree[B] 同样减去 2。加了多少次，就会被减去多少次，拓扑排序的队列入度清零逻辑依然严丝合缝！

选学：什么情况下必须去重？

如果题目要求计算“从 A 到 B 有多少条不同的路径”（组合计数类 DP：ways[v] = (ways[v] + ways[u]) % mod），此时重边会导致方案数翻倍。这种情况下，就必须在建新图前，把边存进 std::set 或者排序后 unique，剔除掉重复的有向边。

七、连通性算法多维特征对比

割点、桥及两类 DCC 的实现见《双连通分量：割点、桥与树形缩点》。