强连通分量与缩点

若已学过《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)：有向图中的一个极大子图，在这个子图内的任意两个节点都能互相到达。单独的一个节点也被视为一个强连通分量。

先抓住重点： 同一个 SCC 内任意两点都能“有去有回”；两个不同的 SCC 之间不能互相到达，否则它们就该合成一个更大的 SCC。

算法应用背景（缩点）：

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

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

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

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

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

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

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

• dfn[u]（DFS Number / 时间戳）：表示节点 $u$ 在 DFS 过程中首次被访问的次序。该值一旦分配，永不改变。
• low[u]（追溯值）：表示从节点 $u$ 出发，先沿 DFS 树向下走零步或多步，再通过至多一条指向当前搜索栈内节点的边，所能触及的最小 dfn。它会在回溯时不断由子节点向父节点传递。

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 编号。

课堂手推： 画出 1→2→3→1，再从 3 连一条边到 4。按访问顺序记录 dfn、low 和栈，看看为什么 4 先单独出栈，1、2、3 随后一起出栈。

三、标准求解算法与模板

易错点分析： 在判断已访问节点时，严格使用 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])$。

  开始时令每个分量的 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]]++;
        }
    }
}

五、2-SAT 问题与逻辑约束的图论降维（选学）

1. 问题背景：非黑即白的抉择

很多时候，我们面临的不是在图中找路径，而是做一系列“二选一”的逻辑决策。

比如有 $N$ 个同学（布尔变量，只能选去或者不去），教练给出了一系列约束条件： “张三和李四，至少去一个！” “如果王五不去，那赵六绝对不能去！”

2-SAT (2-Satisfiability) 问题就是指：所有的约束条件都可以转化成两个变量的“或”关系（析取）。我们需要给每个变量分配真 (1) 或假 (0)，让所有条件同时满足。如果能，给出一种方案；如果不能，立刻判定无解。

2. 状态分配与建图：寻找“蕴含边”

既然每个同学 $i$ 只有两种状态，我们直接把图的规模翻倍：

• 真节点 $i$：代表第 $i$ 个同学去。
• 假节点 $i'$：代表第 $i$ 个同学不去。（代码中通常设为 $i+n$）

核心推导：将任何逻辑关系拍扁成有向推导边 (蕴含边)。 在 2-SAT 中，有向边 $u \to v$ 的物理意义非常直接：“如果 $u$ 成立，那么 $v$ 必须成立”。

我们拿最经典的约束“同学 A 或 同学 B 至少去一人 ($A \lor B$)”来拆解：

• 如果 A 不去，为了满足条件，B 必须去。连边：$A' \to B$。
• 如果 B 不去，为了满足条件，A 必须去。连边：$B' \to A$。 这两条边互为逆否命题，必须成对添加。

如果约束是“A 必须去”怎么连？可以视为 $A \lor A$：

• 如果 A 不去，A 必须去。连边：$A' \to A$。这就暗示了走上 $A'$ 是绝路，顺着边终将导向矛盾或被迫折返至 A。

3. 判断矛盾：强连通分量 (SCC) 的判决

有向图建好后，图中的一条路径 $u \leadsto v$ 就代表逻辑链条：“如果选了 $u$，顺藤摸瓜，最后注定要选 $v$”。

如果图中出现了环，这意味着环上的状态“同生共死”：只要选中其中一个，就必须同时选中其余状态；也可以全部不选。这正是 SCC 的物理意义！ 那么什么时候会无解（自相矛盾）？ 如果变量 $i$ 的真节点 $i$ 和假节点 $i'$ 落在了同一个 SCC 里！

这就意味着：图中存在一条路从 $i \leadsto i'$，又有一条路从 $i' \leadsto i$。“如果选你去，就会推导出你不去；如果你不去，又推导出你必须去。”逻辑死锁，彻底无解。反之，只要没有任何一个变量的真假节点在同一个 SCC 中，就必定有解。

4. 赋值方向：Tarjan 编号的隐藏福利

既然有解，我到底该让变量 $i$ 为真还是为假？ 在推导链条中，如果存在路径 $i \leadsto i'$，说明选“真”会惹祸上身（被迫推导到“假”），所以我们得选“假”。 为了安全，对每对互为否定的状态，我们选择所在 SCC 拓扑序靠后的那一个；结合成对的逆否蕴含边，这样的选择不会违背约束。注意，“靠后”不等于每个选中的状态都没有出边。

重点来了：我们不需要手写拓扑排序！ 回忆一下 Tarjan 的出栈机制：只有当一个 SCC 内部及其所有能到达的下游分支都搜索完后，这个 SCC 的根才会被判定出栈。 这意味着，越先出栈的 SCC，位于拓扑序的越末端。 也就是说，scc[x] 的编号越小，说明它越早出栈，拓扑序越靠后！

所以，对变量 $i$，我们直接对比真节点 $i$ 和假节点 $i'$ 的 SCC 编号：

• 如果 scc[i] < scc[i']：真节点的拓扑序更靠后，更安全，所以赋值为 1（真）。
• 否则：赋值为 0（假）。

不需要任何多余的建图和搜索，这几行判断就是 Tarjan 赐予我们的隐藏福利。

这个大小关系依赖于本模板“出栈时递增编号”的约定；若换成 Kosaraju 或调整编号顺序，比较方向可能相反，不能直接照搬。

5. 课堂手推与验证

假设有变量 1 和 2。要求满足两个条件：

1. 两人至少去一个 ($1 \lor 2$)
2. 1 必须去 ($1 \lor 1$)

映射规则：真节点为 $i$，假节点为 $i+2$。 建边：

• 条件 1 ($1 \lor 2$)：$3 \to 2$ ($1' \to 2$)，并且 $4 \to 1$ ($2' \to 1$)。
• 条件 2 ($1 \lor 1$)：$3 \to 1$ ($1' \to 1$)。

运行 Tarjan： 在这个图 (3->2, 4->1, 3->1) 中，没有环，每个点都是独立的 SCC。 1 和 2 没有任何出边，一定是第一批出栈的，它们的 scc 编号最小。 而 3 能走到 1 和 2，一定是后出栈的，scc[3] 会大于 scc[1]。 判定： scc[1] < scc[3]？是的，1 先出栈。所以变量 1 取真（去）。 按下面代码从 1 到 4 的访问顺序，scc[2]=2 < scc[4]=4，所以变量 2 也取 1。验证：两人都去，满足 1 必去，也满足 1 或 2 至少去一个。

6. 完整 2-SAT 模板代码

💡 【实战程序】 2-SAT 问题求解模板。 输入说明：第一行 $n, m$ 表示布尔变量数（编号 $1 \dots n$）和约束数。接下来 $m$ 行，每行格式 i a j b，表示“变量 $i$ 状态为 $a$，或者 变量 $j$ 状态为 $b$”（$a, b \in \{0,1\}$）。 输出说明：有解输出 POSSIBLE 并给出 $n$ 个变量的 0/1 赋值；无解输出 IMPOSSIBLE。

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

const int N = 200005; // 注意：有真假两个状态，节点数开到原变量数的两倍
vector<int> node[N];

int dfn[N], low[N], instk[N], scc[N];
int id = 0, sc = 0;
stack<int> stk;

// Tarjan 核心完全没变
void dfs(int u) {
    dfn[u] = low[u] = ++id;
    stk.push(u);
    instk[u] = 1;
    for (int v : node[u]) {
        if (!dfn[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (instk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        sc++;
        int x;
        do {
            x = stk.top();
            stk.pop();
            instk[x] = 0;
            scc[x] = sc;
        } while (x != u);
    }
}

void solve() {
    int n, m;
    if (!(cin >> n >> m)) return;
    
    for (int k = 1; k <= m; k++) {
        int i, a, j, b;
        cin >> i >> a >> j >> b;
        
        // 节点映射：变量 x 的真状态节点标号为 x，假状态节点标号为 x + n
        int real_i = a ? i : i + n;
        int not_i = a ? i + n : i;
        
        int real_j = b ? j : j + n;
        int not_j = b ? j + n : j;
        
        // 连蕴含边：如果不满足 i 的条件，就必须满足 j 的条件；反之亦然
        node[not_i].push_back(real_j);
        node[not_j].push_back(real_i);
    }
    
    // 图一共有 2n 个节点，跑一遍 Tarjan
    for (int i = 1; i <= 2 * n; i++) {
        if (!dfn[i]) dfs(i);
    }
    
    // 降维打击 1：同一个变量的真假状态在同一个 SCC 内，绝对矛盾，无解
    for (int i = 1; i <= n; i++) {
        if (scc[i] == scc[i + n]) {
            cout << "IMPOSSIBLE\n";
            return;
        }
    }
    
    // 降维打击 2：利用 scc 编号反向拓扑序确定赋值
    cout << "POSSIBLE\n";
    for (int i = 1; i <= n; i++) {
        // scc 越小，说明越早出栈，拓扑序越靠后，越安全
        if (scc[i] < scc[i + n]) {
            cout << 1 << (i == n ? "" : " ");
        } else {
            cout << 0 << (i == n ? "" : " ");
        }
    }
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}
/*
输入样例：
2 2
1 1 2 1
1 1 1 1

输出样例：
POSSIBLE
1 1
*/

上面是本代码的实际输出。可行解不唯一，1 0 也满足这些约束；这类题通常用 SPJ 检查合法性，不要求逐字匹配某一组赋值。

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