bitworld 的博客
Tarjan全家桶
bitworld 最强壮的男人 SU @ 2025-9-1 16:55:45

Tarjan全家桶

前言

图论领域，Robert Tarjan的名字与一系列高效、深刻的算法紧密相连。

其中，以他名字命名的Tarjan算法，并非特指单一算法，而是一套基于深度优先搜索（DFS）思想，通过巧妙维护节点时间戳与追溯值来解决图连通性问题的算法框架。精通Tarjan算法的各种变体及其应用，是构建完备图论知识体系、提升解题能力的关键一环。

本文旨在系统性地梳理Tarjan算法在竞赛中的全部核心用法，从其理论基础出发，深入探讨其在求解强连通分量、割点与桥、双连通分量等问题上的应用，并结合代码实现与经典例题，提供一份内容翔实、服务于实战的指南。

1. 核心思想： $dfn$ 与 $low$ 数组

Tarjan系列算法的精髓在于对深度优先搜索过程的创造性利用。它不仅记录节点的访问顺序，更通过两个核心数组—— $dfn$ （Depth First Number）和 $low$ （Low-link value），来量化和追踪图中节点间的连通关系。理解这两个数组的定义与维护方式，是掌握所有Tarjan算法变体的前提。

1.1 深度优先搜索树

在任意连通图上进行深度优先搜索，所有遍历经过的边会构成一棵生成树（对于非连通图则是生成森林）。我们将这棵树称为DFS树。DFS树的结构是Tarjan算法分析的基础。根据DFS的进程，图中的边可以被分为四类：

树边（Tree Edge）：DFS过程中实际经过的边，构成DFS树的实体。从节点 $u$ 访问到一个未访问过的新节点 $v$ ，则 $(u, v)$ 是一条树边。
前向边（Forward Edge）：从DFS树的一个节点 $u$ 指向其在树中的一个非直接子孙节点 $v$ 的边。
返祖边/后向边（Back Edge）：从DFS树的一个节点 $u$ 指向其在树中的一个祖先节点 $v$ 的边。返祖边的存在，标志着图中环的出现。
横叉边（Cross Edge）：从DFS树的一个节点 $u$ 指向另一节点 $v$ ，但 $v$ 并非 $u$ 的祖先或子孙。在有向图中，横叉边可能从一个子树指向另一个已经访问完毕的子树；在无向图中，由于DFS的性质，所有非树边必然是返祖边，不存在横叉边。

Tarjan算法的核心，就是通过分析返祖边和横叉边对DFS树结构的影响，来判断图的连通性。

1.2 $dfn$ 数组：时间戳

$dfn$ 数组，或称为 discovery time / timestamp，记录的是每个节点在DFS过程中首次被访问的顺序。我们通常用一个全局计数器 ts 或 cnt 来实现，每当访问一个新节点时，就将当前的计数器值赋给该节点的 $dfn$ 值，然后计数器加一。

$dfn[u]$ 的值越小，说明节点 $u$ 在DFS中被访问得越早。它为每个节点提供了一个独一无二的、反映遍历顺序的身份标识。

1.3 $low$ 数组：追溯值

$low$ 数组，或称为 low-link value，是Tarjan算法的灵魂。 $low[u]$ 定义为从节点 $u$ 出发，通过其DFS子树中的节点，能够到达的所有节点中， $dfn$ 值的最小值。

这个定义包含两层含义：

出发点：分析的起点是节点 $u$ 。
可达路径：路径可以沿着DFS树的树边向下走，到达 $u$ 的任意子孙节点，然后再从这些子孙节点出发，最多再经过一条非树边（通常是返祖边），到达一个节点 $v$ 。
目标：在所有可达的节点 $v$ 中，寻找最小的 $dfn[v]$ ，这个最小值就是 $low[u]$ 。

直观解释： $low[u]$ 代表了节点 $u$ "最早能回溯到哪个祖先"。如果把DFS树想象成一个家族的族谱， $dfn$ 值就是出生时间， $low[u]$ 就是 $u$ 及其所有后代能找到的、辈分最高（即出生最早， $dfn$ 最小）的那个祖先的时间戳。

1.4 $low$ 数组的计算

$low$ 数组的值是在DFS的回溯阶段（即递归返回时）计算并更新的。其计算逻辑如下：

首先，当一个节点 $u$ 首次被访问时，它的 $low$ 值被初始化为其自身的 $dfn$ 值。这表示，在不考虑任何非树边的情况下，节点 $u$ 能到达的最早节点就是它自己。

low[u] = dfn[u]

接下来，在DFS过程中，当我们遍历节点 $u$ 的邻居 $v$ 时，根据 $v$ 的状态进行分类讨论：

$v$ 是 $u$ 在DFS树上的子节点（树边）：我们首先递归地对 $v$ 进行DFS，即 dfs(v)。当 dfs(v) 返回后， $v$ 的 $low$ 值 low[v] 已经计算完毕。由于 $v$ 是 $u$ 的子孙，从 $u$ 出发可以到达 $v$ 能到达的所有地方。因此， $v$ 能追溯到的最早祖先， $u$ 也同样能追溯到。所以，我们用 $low[v]$ 来更新 $low[u]$ 。
$low[u] = \min(low[u], low[v])$
$v$ 是 $u$ 在DFS树上的祖先（返祖边），且 $v$ 在当前路径的栈中：这条返祖边 $(u, v)$ 提供了一条从 $u$ 直接回到其祖先 $v$ 的路径。这意味着 $u$ 至少可以追溯到 $v$ 。因此，我们用 $v$ 的时间戳 $dfn[v]$ 来更新 $low[u]$ 。
$low[u] = \min(low[u], dfn[v])$
（在求解强连通分量时，需要额外判断 $v$ 是否在栈中；而在求解割点和桥时，由于是无向图，只需判断 $v$ 不是 $u$ 的父节点即可。）

通过以上两条规则，在DFS回溯的过程中， $low$ 值被层层向上传递和更新，最终准确地反映了每个节点所能追溯到的最早的祖先节点的时间戳。

2. 应用一：有向图的强连通分量 (SCC)

强连通分量（Strongly Connected Component, SCC）是Tarjan算法最经典、最广为人知的应用。

2.1 概念定义

在一个有向图 $G$ 中，一个强连通分量是图的一个极大子图，其中任意两个节点 $u, v$ 都是相互可达的，即存在从 $u$ 到 $v$ 的路径，也存在从 $v$ 到 $u$ 的路径。

“极大性”意味着，如果再加入图中任何一个不属于该SCC的节点，这个子图就不再强连通。

2.2 底层原理

Tarjan算法寻找SCC的原理，是基于DFS树和 $low$ 数组的一个关键观察：一个强连通分量的所有节点，必然是DFS树中某一棵子树的节点集合，且这个SCC的根节点（在这棵子树中，也是整个SCC中第一个被访问的节点）满足 $dfn[u] == low[u]$ 。

为什么这个条件成立？

$low[u] < dfn[u]$ 意味着 $u$ 或其子树中的某个节点，可以通过一条返祖边到达 $u$ 的一个严格祖先。这说明 $u$ 和这个祖先处在同一个更大的环路中，因此 $u$ 不可能是一个SCC的根。
$dfn[u] == low[u]$ 意味着从 $u$ 出发，无论通过其子树走多远，再经过返祖边，最远也只能回到 $u$ 自己，无法到达 $u$ 的任何祖先。这表明 $u$ 是其所在连通区域中，按照DFS顺序最早被发现的节点。它就像一个“门户”，从它和它的子树无法“逃逸”到更早的节点。因此， $u$ 成为了一个SCC的根节点。

算法通过一个栈来辅助识别SCC的成员。当DFS访问节点时，将节点入栈。如果一个节点 $u$ 被判定为一个SCC的根（即 $dfn[u] == low[u]$ ），那么当前栈中所有在 $u$ 之上（包括 $u$ ）的节点，就构成了以 $u$ 为根的这个强连通分量。此时，我们只需将这些节点不断出栈，直到 $u$ 被弹出，所有弹出的节点就组成了一个SCC。

2.3 关键代码实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 100005;
vector<int> adj[N];
int dfn[N], low[N], ts;
int stk[N], top;
bool is[N]; // is in stack
int scc[N], cnt; // scc[i]是i所属的scc编号, cnt是scc总数

void tj(int u) {
    dfn[u] = low[u] = ++ts;
    stk[++top] = u;
    is[u] = 1;

    for (int v : adj[u]) {
        if (!dfn[v]) { // 树边
            tj(v);
            low[u] = min(low[u], low[v]);
        } else if (is[v]) { // 返祖边或指向栈中节点的横叉边
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        cnt++;
        int y;
        do {
            y = stk[top--];
            is[y] = 0;
            scc[y] = cnt;
        } while (y != u);
    }
}

void solve(int n) {
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tj(i);
        }
    }
}

代码解析：
- dfn 和 low 数组如前所述。ts 是全局时间戳计数器。
- stk 是一个手动实现的栈，top 是栈顶指针。is 数组用于在 $O(1)$ 时间内判断一个节点是否在栈中。
- scc 数组记录每个节点所属的SCC编号，cnt 是SCC的总数。
- tj(u) 函数是核心的DFS过程。
- if (!dfn[v]) 分支处理树边，递归调用后，用子节点的 low 值更新父节点的 low 值。
- else if (is[v]) 分支处理指向栈中节点的边。这包括了返祖边和部分横叉边。用 dfn[v] 更新 low[u] 是因为，既然 $v$ 还在栈里，说明 $v$ 是 $u$ 的一个祖先（或者在另一个尚未完成的子树里，但两者通过横叉边连接，暗示可能在同一个SCC中），这条边提供了一条“捷径”回到更早的节点。
- if (dfn[u] == low[u]) 是判定SCC根的时刻。一旦成立，就从栈顶不断弹出节点，直到 $u$ 本身被弹出。所有弹出的节点都属于同一个新发现的SCC。
复杂度分析：
- 时间复杂度：每个节点和每条边都只被访问一次，因此时间复杂度为 $O(V+E)$ ，其中 $V$ 是节点数， $E$ 是边数。
- 空间复杂度：邻接表、dfn, low, stk, is, scc 数组都需要 $O(V)$ 的空间，递归栈的深度最坏情况下也是 $O(V)$ ，总空间复杂度为 $O(V+E)$ 。

2.4 图的缩点

求解SCC的一个直接应用是缩点（Graph Condensation）。将原图的每个强连通分量“压缩”成一个单一的超级节点，原图中连接两个不同SCC的边，在缩点后的新图中就成为连接对应超级节点的边。

由于SCC内部节点可以互相到达，而在SCC之间不存在环路（否则这些SCC会合并成一个更大的SCC），所以缩点后的图是一个有向无环图（DAG）。这个性质非常重要，它允许我们在新图上进行拓扑排序、动态规划等DAG相关的操作。

缩点的步骤：

使用Tarjan算法求出所有SCC，并为每个节点标记其所属的SCC编号。
建立新图。遍历原图的每一条边 $(u, v)$ 。
如果 $u$ 和 $v$ 属于不同的SCC（即 scc[u] != scc[v]），则在新图中从 scc[u] 对应的超级节点向 scc[v] 对应的超级节点连一条边。
为了避免重边，可以使用 std::set 或排序去重的方式来构建新图的邻接表。

2.5 典型实例分析

例题: Codeforces 427C - Checkposts

题意概括：给定一个有 $N$ 个节点、 $M$ 条边的有向图，每个节点上建立一个检查站需要一定的花费 $cost_i$ 。要求在图中建立一些检查站，使得从图中任意一个节点出发，都能到达一个建有检查站的节点。目标是求出满足条件的最小总花费，以及在最小花费下的方案数。
解题思维： “从任意节点出发都能到达一个检查站”，这个条件可以转换成：对于图中的每一个节点，其所在的强连通分量内，至少要有一个检查站。这是因为，一个SCC内的所有节点都是相互可达的。只要其中一个节点能到达一个检查站（无论是在SCC内部还是外部），那么SCC内的所有节点就都能通过它间接到达那个检查站。反之，如果SCC内的所有节点都无法到达任何检查站，那么这个SCC就不满足条件。最经济的做法，是在每个SCC内部，选择建立一个检查站。为了使总花费最小，我们应该在每个SCC内部，选择那个花费最小的节点来建立检查站。

问题就转化为：
1. 对原图求强连通分量。
2. 对每一个SCC，找出其中所有节点的最小花费。
3. 将所有SCC的最小花费相加，得到总的最小花费。
4. 对于每个SCC，统计其中拥有最小花费的节点的数量。
5. 根据乘法原理，将每个SCC的最小花费节点数量相乘，得到总的方案数。

核心代码实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 100005;
const int MOD = 1e9 + 7;
vector<int> adj[N];
int c[N]; // cost
int dfn[N], low[N], ts;
int stk[N], top;
bool is[N];
vector<int> scc[N];
int cnt;

void tj(int u) {
    dfn[u] = low[u] = ++ts;
    stk[++top] = u;
    is[u] = 1;

    for (int v : adj[u]) {
        if (!dfn[v]) {
            tj(v);
            low[u] = min(low[u], low[v]);
        } else if (is[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        cnt++;
        int y;
        do {
            y = stk[top--];
            is[y] = 0;
            scc[cnt].push_back(y);
        } while (y != u);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    cin >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tj(i);
    }

    ll ans_c = 0;
    ll ans_w = 1;

    for (int i = 1; i <= cnt; i++) {
        int min_c = INT_MAX;
        int num = 0;
        for (int node : scc[i]) {
            min_c = min(min_c, c[node]);
        }
        for (int node : scc[i]) {
            if (c[node] == min_c) {
                num++;
            }
        }
        ans_c += min_c;
        ans_w = (ans_w * num) % MOD;
    }

    cout << ans_c << " " << ans_w << endl;

    return 0;
}

代码解释：
- Tarjan算法部分与模板基本一致，只是在找到一个SCC后，将其所有成员节点存入 scc[cnt] 这个vector中，而不是只标记编号。
- 主函数中，在求完所有SCC后，遍历每个SCC。
- 对每个 scc[i]，先找到最小花费 min_c，再统计等于 min_c 的节点数 num。
- 累加 min_c 到总花费 ans_c，并将 num 乘入总方案数 ans_w（注意取模）。

3. 应用二：无向图的割点与桥

在无向图中，Tarjan算法同样可以用来寻找关键的节点和边，即割点（Articulation Points）和桥（Bridges）。它们在网络可靠性、基础设施规划等领域有重要应用。

3.1 概念定义

割点（Cut Vertex）：在一个无向连通图中，如果移除一个节点 $u$ 以及所有与它相连的边，导致图分裂成两个或更多个连通分量，那么节点 $u$ 就是一个割点。
桥（Bridge / Cut Edge）：在一个无向连通图中，如果移除一条边 $(u, v)$ ，导致图分裂成两个连通分量，那么边 $(u, v)$ 就是一条桥。

3.2 底层原理

求解割点和桥的原理与SCC类似，也是基于对DFS树和 $low$ 数组的分析，但判断条件有所不同。

桥的判定：一条边 $(u, v)$ （假设 $u$ 是 $v$ 在DFS树中的父节点）是桥，当且仅当 $v$ 的子树中没有任何一条返祖边能够连接到 $u$ 或 $u$ 的祖先。如果存在这样的返祖边，那么即使断开 $(u, v)$ ，从 $v$ 的子树出发仍然可以通过这条返祖边绕回 $u$ 或其祖先，图依然保持连通。这个条件的数学表达是：

low[v] > dfn[u]

$low[v]$ 表示 $v$ 子树能追溯到的最早的节点的 $dfn$ 。如果这个值比 $dfn[u]$ 还大，说明 $v$ 子树能到达的最早节点就是 $u$ 的某个子孙（可能是 $v$ 自己），但绝不可能是 $u$ 或 $u$ 的祖先。因此，边 $(u, v)$ 是从 $u$ 到达 $v$ 子树的唯一通道，是为桥。

割点的判定：一个节点 $u$ 是割点，需要分两种情况讨论：

$u$ 是DFS树的根节点：如果根节点 $u$ 有两个或更多的子树，那么移除 $u$ 后，这些子树之间将失去联系（因为它们只能通过 $u$ 连接），图会分裂。因此，DFS树的根是割点，当且仅当它拥有至少两个子节点。
$u$ 不是DFS树的根节点：如果 $u$ 至少存在一个子节点 $v$ ，使得 $v$ 的整个子树都无法通过返祖边连接到 $u$ 的严格祖先（可以连接到 $u$ 自己，但不能更早）。移除 $u$ 后， $v$ 的子树将与图的其余部分（包括 $u$ 的父节点和兄弟子树）失去联系。这个条件的数学表达是：存在一个子节点 $v$ ，使得
$low[v] \ge dfn[u]$
$low[v] \ge dfn[u]$ 意味着 $v$ 子树能追溯到的最早节点就是 $u$ 本身，而无法到达 $u$ 的任何祖先。因此， $u$ 是其父节点与 $v$ 子树之间联系的唯一枢纽。一旦移除 $u$ ，这条联系就断了。

注意与桥的判定的细微差别：桥是 >，割点是 ≥。这是因为，如果 $low[v] == dfn[u]$ ，意味着 $v$ 的子树最远能回到 $u$ ，但不能更远。此时边 $(u, v)$ 不是桥（因为有另一条路径从 $v$ 子树回到 $u$ ），但 $u$ 依然是割点（因为 $v$ 子树与 $u$ 的父节点之间，仍然必须通过 $u$ ）。

3.3 关键代码实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 100005;
vector<int> adj[N];
int dfn[N], low[N], ts;
bool ap[N]; // articulation point
vector<pair<int, int>> br; // bridges

void tj(int u, int p) { // p is the parent of u in DFS tree
    dfn[u] = low[u] = ++ts;
    int ch = 0; // children in DFS tree

    for (int v : adj[u]) {
        if (v == p) continue; // 不走直接指向父节点的边
        if (!dfn[v]) {
            ch++;
            tj(v, u);
            low[u] = min(low[u], low[v]);

            // 判定桥
            if (low[v] > dfn[u]) {
                br.push_back({min(u, v), max(u, v)});
            }
            // 判定割点 (非根节点)
            if (p != 0 && low[v] >= dfn[u]) {
                ap[u] = true;
            }
        } else { // 返祖边
            low[u] = min(low[u], dfn[v]);
        }
    }

    // 判定割点 (根节点)
    if (p == 0 && ch > 1) {
        ap[u] = true;
    }
}

void solve(int n) {
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tj(i, 0); // 根节点的父节点设为0
        }
    }
}

代码解析：
- tj(u, p) 函数增加了一个参数 p，表示 $u$ 的父节点。在遍历 $u$ 的邻居时，跳过 v == p 的情况，以避免将DFS树的双向边误判为返祖边。
- ch 变量用于统计节点 $u$ 在DFS树中的子节点数量，仅用于根节点的割点判定。
- if (low[v] > dfn[u]) 直接判定桥。
- if (p != 0 && low[v] >= dfn[u]) 判定非根节点的割点情况。
- if (p == 0 && ch > 1) 在函数末尾判定根节点的割点情况。
- ap 数组标记一个节点是否为割点，br 存储找到的所有桥。
复杂度分析：
- 与SCC版本相同，每个节点和边被访问一次，时间复杂度为 $O(V+E)$ ，空间复杂度为 $O(V+E)$ 。

3.4 典型实例分析

例题: POJ 3177 - Redundant Paths (这是一个经典问题，很多平台有类似题目)

题意概括：给定一个有 $F$ 个牧场（节点）和 $R$ 条道路（边）的无向图，该图可能不是连通的。现在需要添加一些新的道路，使得整个图变成边双连通的（即图中没有桥）。求最少需要添加几条边。
解题思维：一个图是边双连通的，等价于图中不存在桥。我们的目标是消除所有桥。如何消除桥？一条边 $(u, v)$ 是桥，意味着断开它会使图分裂。要修复它，我们需要在 $(u, v)$ 两端所连接的两个连通块之间，再添加一条边，形成一个环。这个环的存在使得即使 $(u, v)$ 断开，两个连通块依然可以通过新加的边保持连通。

此题的解决方案是进行“缩点”，但这次是基于“边双连通分量”的缩点。
1. 求桥：首先用Tarjan算法找到图中所有的桥。
2. 缩点：将所有的桥断开，原图会分裂成若干个连通块。每个这样的连通块就是一个边双连通分量 (Edge Biconnected Component, E-BCC)。我们将每个E-BCC缩成一个超级节点。
3. 建树：原图中的桥，在缩点后就变成了连接两个超级节点的边。由于桥被移除后图无环，这些超级节点和连接它们的边会构成一棵树（或森林，如果原图不连通）。
4. 树上贪心：问题转化为：给定一棵（或多棵）树，最少需要加几条边，使得整个图连通且无桥。
  - 首先，如果有多棵树（原图有多个连通分量），我们需要先加边把它们连成一棵大树。假设有 $k$ 个连通分量，需要加 $k-1$ 条边。
  - 现在考虑在一棵树上加边。我们的目标是让树变成一个边双连通图。观察发现，树的叶子节点是“最脆弱”的。每次加一条边，连接两个叶子节点，可以消除这两片叶子到它们LCA路径上的所有桥。最优的策略是，每次连接两个“悬挂”的叶子节点。
  - 一个更简单的结论是：在一棵树上，要使其边双连通，需要添加的边数是 (叶子节点数量 + 1) / 2。每次我们用一条边连接两个叶子节点，相当于满足了这两个叶子的连通性需求。
综合起来，算法步骤如下：
1. 用Tarjan算法找出所有的桥。
2. 遍历所有节点，用DFS或BFS，不经过桥，对图进行染色（或标记），划分出所有的E-BCC，并统计E-BCC的数量。
3. 在划分E-BCC的过程中，统计每个E-BCC的“度”，即有多少条桥连接到这个E-BCC。
4. 度为1的E-BCC，在缩点后的树中就是叶子节点。统计这样的叶子节点的数量 leaves。
5. 如果E-BCC总数（连通分量数）为1，则答案为0。
6. 否则，最少需要加的边数是 (leaves + 1) / 2。

核心代码实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 5005;
vector<pair<int, int>> adj[N]; // {neighbor, edge_id}
int dfn[N], low[N], ts;
bool br[N * 4]; // is bridge (edge_id)

int c[N], cnt; // c[i]是i所属的E-BCC编号
int deg[N]; // E-BCC的度

void tj(int u, int eid) {
    dfn[u] = low[u] = ++ts;
    for (auto& edge : adj[u]) {
        int v = edge.first;
        int id = edge.second;
        if (id == eid) continue;
        if (!dfn[v]) {
            tj(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                br[id] = true;
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void dfs(int u) {
    c[u] = cnt;
    for (auto& edge : adj[u]) {
        int v = edge.first;
        int id = edge.second;
        if (br[id] || c[v]) continue;
        dfs(v);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int f, r;
    cin >> f >> r;
    for (int i = 0; i < r; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    for (int i = 1; i <= f; i++) {
        if (!dfn[i]) tj(i, -1);
    }

    for (int i = 1; i <= f; i++) {
        if (!c[i]) {
            cnt++;
            dfs(i);
        }
    }

    if (cnt == 1) {
        cout << 0 << endl;
        return 0;
    }

    for (int u = 1; u <= f; u++) {
        for (auto& edge : adj[u]) {
            int v = edge.first;
            if (c[u] != c[v]) {
                deg[c[u]]++;
            }
        }
    }

    int leaves = 0;
    for (int i = 1; i <= cnt; i++) {
        // 每个桥会被统计两次，所以度数要除以2
        if (deg[i]/2 == 1) {
            leaves++;
        }
    }

    cout << (leaves + 1) / 2 << endl;

    return 0;
}

代码解释：
- 为了方便标记桥，邻接表存储了 {neighbor, edge_id}。
- 第一步 tj 函数求出所有桥，并标记在 br 数组中。
- 第二步 dfs 函数用于划分E-BCC。它只在非桥的边上进行遍历，从而将同一个E-BCC内的节点染上相同的颜色 cnt。
- 第三步，统计每个E-BCC的度。遍历所有边，如果一条边的两端属于不同的E-BCC，说明这条边就是桥，它连接的两个E-BCC的度都加1。注意这里 deg 的计算方式，遍历所有节点的所有边，如果端点颜色不同就给自己的颜色+1度。
- 第四步，统计叶子节点。一个E-BCC在缩点后的树中是叶子，当且仅当它只与一条桥相连。由于每条桥连接两个E-BCC，在度数统计中，每个桥会使两端的E-BCC度数各加1，所以我们统计 deg[i]/2 == 1 的E-BCC数量。
- 最后，根据公式 (leaves + 1) / 2 计算答案。

4. 无向图双连通性深度剖析

在前一部分，我们已经探讨了割点与桥，它们是理解无向图双连通性的基础。现在，我们将深入研究由这些概念引出的结构——双连通分量（Biconnected Components, BCC）。双连通分量分为两种：边双连通分量（E-BCC）和点双连通分量（V-BCC）。

4.1 边双连通分量 (E-BCC)

概念回顾：一个边双连通图是任意移除一条边都不会导致图不连通的图。等价地说，一个图是边双连通的，当且仅当它没有桥。一个图的极大边双连通子图被称为边双连通分量（E-BCC）。
求解与缩点：求解E-BCC的过程在上一部分的例题 [POJ 3177] 中已经有所体现。其核心步骤是：
1. 通过Tarjan算法找到图中所有的桥。
2. 将所有桥从图中“逻辑上”移除。
3. 剩下的图会由若干个连通块组成，每一个连通块就是一个E-BCC。
4. 可以通过一次新的DFS或BFS（只在非桥边上遍历）来为每个节点染色，从而确定其所属的E-BCC。
缩点后的图，即将每个E-BCC视为一个超级节点，原图中的桥作为连接这些超级节点的边，所形成的结构必然是一棵树或森林。这棵树被称为Block-Cut Tree的简化版（只考虑了桥），它将原图的边连通性问题转化为了树上的问题，从而可以利用树的各种优美性质来求解。

4.2 点双连通分量 (V-BCC)

点双连通分量是比E-BCC更精细、应用更广泛的概念。

概念定义：一个点双连通图是节点数大于2，且任意移除一个节点都不会导致图不连通的图。等价地说，一个图是点双连通的，当且仅当它没有割点。一个图的极大点双连通子图被称为点双连通分量（V-BCC），也常被称为“块”（Block）。
V-BCC的性质：
1. V-BCC内部，任意两点之间至少存在两条点不相交的路径（除了起点和终点）。
2. 两个V-BCC之间最多只有一个公共点，这个公共点必然是割点。
3. 一个割点可以属于多个V-BCC。
4. 非割点只属于一个V-BCC。
5. 一条边恰好属于一个V-BCC。
底层原理与求解 Tarjan算法求解V-BCC的核心，仍然是利用 low[v] >= dfn[u] 这个割点判定条件。当在DFS中从节点 $u$ 访问其子节点 $v$ 后，发现 low[v] >= dfn[u]，这不仅意味着 $u$ 是一个（潜在的）割点，更重要的是，它标志着一个V-BCC被完整地探索完毕了。

这个V-BCC由以下部分组成：
1. 子节点 $v$ 及其整个DFS子树。
2. 父节点 $u$ 。
3. 连接这些节点形成一个“块”的所有边。
为了准确地捕获这些V-BCC的成员，我们不能再使用节点栈，因为节点（特别是割点）可能属于多个V-BCC。正确的做法是维护一个边栈。当DFS遍历一条边时，就将该边入栈。

当 low[v] >= dfn[u] 条件满足时，我们就从边栈顶不断弹出边，直到边 $(u, v)$ 被弹出为止。所有这些弹出的边，以及它们所连接的节点，就构成了一个新的V-BCC。

4.3 关键代码实现 (V-BCC)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 200005, M = 1000005;
vector<int> adj[N];
int dfn[N], low[N], ts;
pair<int, int> stk[M];
int top;
vector<vector<int>> vcc;
int cnt;

void tj(int u, int p) {
    dfn[u] = low[u] = ++ts;

    for (int v : adj[u]) {
        if (v == p) continue;
        
        if (!dfn[v]) {
            stk[++top] = {u, v}; // 边入栈
            tj(v, u);
            low[u] = min(low[u], low[v]);

            if (low[v] >= dfn[u]) {
                cnt++;
                vcc.resize(cnt + 1);
                set<int> nodes;
                pair<int, int> edge;
                do {
                    edge = stk[top--];
                    nodes.insert(edge.first);
                    nodes.insert(edge.second);
                } while (edge.first != u || edge.second != v);
                
                for(int node : nodes) {
                    vcc[cnt].push_back(node);
                }
            }
        } else if (dfn[v] < dfn[u]) { // 仅当v是u的真祖先时才更新
            stk[++top] = {u, v};
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void solve(int n) {
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tj(i, 0);
        }
    }
}

代码解析：
- stk现在是一个 pair 数组，用于存储边。
- vcc 是一个 vector<vector<int>>，vcc[i] 存储第 $i$ 个V-BCC的所有节点。
- tj(u, p) 的逻辑主体与求割点类似。
- if (!dfn[v]) 分支：在递归下降前，将树边 (u, v) 压入栈中。在回溯后，如果满足 low[v] >= dfn[u]，则触发V-BCC的提取。
- do-while 循环不断从栈顶弹出边，并用 std::set 收集这些边所涉及的所有节点（set 自动去重），直到 (u, v) 被弹出。最后将 set 中的节点存入 vcc 中。
- else if (dfn[v] < dfn[u]) 分支：这是一个重要的细节。当遇到一条返祖边 (u, v) 时，它也属于当前的V-BCC，因此也需要入栈。dfn[v] < dfn[u] 条件确保我们只处理指向真正祖先的边，避免在无向图中重复处理同一条边的两个方向。
- 注意：对于只有两个节点一条边的图，它本身就是一个V-BCC。上述代码在 low[v] >= dfn[u] 触发时处理。如果图本身就是点双连通的，那么只会在DFS树的根节点处触发一次或多次，最终将所有边弹出。如果图是孤立点或边，需要根据题意特殊处理。

4.4 Block-Cut Tree (圆方树)

对V-BCC进行缩点，可以得到一个非常强大的数据结构——Block-Cut Tree，也常被形象地称为圆方树。

构建方法：
1. 方点：为每一个V-BCC（块）建立一个新的节点，称为“方点”。
2. 圆点：保留原图中的所有节点，称为“圆点”。
3. 连边：如果原图中的节点 $u$ （一个圆点）属于第 $i$ 个V-BCC，那么就在 $u$ 和代表第 $i$ 个V-BCC的方点之间连一条边。
特别地，如果原图中的一个节点是割点，那么它对应的圆点会连接到多个方点。如果是非割点，则只连接到一个方点。
性质：
1. Block-Cut Tree是一棵真正的树（或森林）。不会有环。
2. 它极好地保留了原图的连通性信息。原图中两点 $a, b$ 之间的所有简单路径，对应到圆方树中，就是圆点 $a$ 和圆点 $b$ 之间唯一路径所经过的圆点集合。
3. 这个性质是圆方树最核心的威力所在：它将复杂的图路径问题，转化为了简单、清晰的树上路径问题。
典型实例分析

例题: 洛谷 P3225 [HNOI2012]矿场搭建

题意概括：给定一个无向图，代表矿区。有两种操作：在某个点设立一个出口，或在两个点之间建立一条新路。目标是，无论哪个矿点塌陷（被删除），任何其他矿点都能通过剩余的路径到达一个出口。求最少需要设置的出口数量，以及在出口数最少的前提下的总方案数。
解题思维：问题可以被翻译为：在图中选择最少的节点作为出口，使得移除任意一个节点后，图的每个连通分量都至少包含一个出口。

这个问题与割点和V-BCC紧密相关。
1. 如果一个矿点 $u$ 不是割点，那么移除它只会影响它自己。图的其余部分仍然连通。
2. 如果一个矿点 $u$ 是割点，移除它会使图分裂。它所连接的各个V-BCC之间会失去联系。
这引导我们对V-BCC进行分析。考虑一个V-BCC：
- Case 1: V-BCC内部没有割点。这意味着这个V-BCC是一个孤立的块（或者是整个图），移除其中任何一点，其余点仍然连通。但是，如果这个块中的两个点 $a, b$ 都塌陷了，就可能出问题。为了保证安全，我们需要在这个V-BCC内设置两个出口。这样，无论哪个点塌陷，总还剩下至少一个出口，并且块内其他点都能到达它。方案数是 $C(|V_{bcc}|, 2)$ 。
- Case 2: V-BCC恰好与一个割点相连。这个V-BCC就像一个“悬挂”在割点上的叶子节点。如果这个割点塌陷，整个V-BCC将与图的其余部分断开连接。为了安全，我们必须在这个V-BCC内部（不包括那个割点）设置一个出口。方案数是 $|V_{bcc}| - 1$ 。
- Case 3: V-BCC与多个割点相连。移除任何一个割点，这个V-BCC内部的点仍然可以通过其他割点与图的其余部分保持连通。因此，这个V-BCC本身是安全的，不需要在其中专门设置出口。
算法流程：
1. 首先处理连通分量。对每个连通分量分别计算答案，然后累加。
2. 对一个连通分量，用Tarjan算法求出所有的V-BCC。
3. 在求V-BCC的过程中，统计每个V-BCC包含的割点数量。
4. 遍历所有V-BCC：
  - 获取V-BCC中的节点集合 nodes 和割点数量 cut_points_count。
  - 如果 cut_points_count == 0，说明这是个孤立的块。需要2个出口，方案数累乘 $C(|nodes|, 2)$ 。
  - 如果 cut_points_count == 1，说明是叶子块。需要1个出口，方案数累乘 $(|nodes| - 1)$ 。
  - 如果 cut_points_count > 1，不需要额外出口。
5. 最终将每个连通分量的答案（出口数相加，方案数相乘）汇总。

核心代码实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1005;
vector<int> adj[N];
int dfn[N], low[N], ts;
int stk[N], top;
vector<vector<int>> vcc;
bool cut[N];
int rt;

void tj(int u) {
    dfn[u] = low[u] = ++ts;
    stk[++top] = u;
    
    if (adj[u].empty()) { // 孤立点
         vcc.push_back({u});
         return;
    }

    int ch = 0;
    for (int v : adj[u]) {
        if (!dfn[v]) {
            ch++;
            tj(v);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                if (u != rt) cut[u] = true;
                vector<int> cur_vcc;
                int y;
                do {
                    y = stk[top--];
                    cur_vcc.push_back(y);
                } while (y != v);
                cur_vcc.push_back(u);
                vcc.push_back(cur_vcc);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (u == rt && ch > 1) cut[u] = true;
}

void solve() {
    int n = 0, m, kase = 0;
    while (cin >> m && m) {
        n = 0;
        vcc.clear();
        for(int i=0; i<N; ++i) adj[i].clear();
        memset(dfn, 0, sizeof(dfn));
        memset(cut, 0, sizeof(cut));
        ts = top = 0;

        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            n = max({n, u, v});
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        int ans_n = 0;
        ll ans_w = 1;
        int comps = 0;
        for (int i = 1; i <= n; i++) {
            if (!dfn[i]) {
                comps++;
                rt = i;
                top = 0; // 每个连通分量清空栈
                tj(i);
            }
        }
        
        for(const auto& cur_vcc : vcc) {
            int cut_cnt = 0;
            for(int node : cur_vcc) {
                if (cut[node]) cut_cnt++;
            }

            if (cut_cnt == 0) {
                if (cur_vcc.size() > 1) {
                   ans_n += 2;
                   ans_w *= (ll)cur_vcc.size() * (cur_vcc.size() - 1) / 2;
                } else { // 孤立点
                   ans_n += 1;
                }
            } else if (cut_cnt == 1) {
                ans_n += 1;
                ans_w *= (cur_vcc.size() - 1);
            }
        }

        cout << "Case " << ++kase << ": " << ans_n << " " << ans_w << endl;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

代码解释：
- 这是一个多 case 的题目。在每个 case 开始前，需要仔细清空所有数据结构。
- 代码使用了节点栈来找V-BCC，这是一种常见的实现方式，但不如边栈严谨。对于这题是够用的。当low[v] >= dfn[u]时，从栈中弹出节点直到v，再加上u，就构成了一个V-BCC。
- 先用一个简单的循环求出所有割点，并标记在cut数组中。
- 主逻辑遍历求出的vcc，对每个V-BCC，统计其中的割点数cut_cnt，然后根据之前分析的三种情况来更新答案。
- 特别注意孤立点和孤立边的处理。在代码中，孤立点被视为一个大小为1的V-BCC，没有割点，需要一个出口。

5. 应用三：最近公共祖先 (LCA)

Tarjan算法还有一个著名的离线应用，即求解树上多个节点对的最近公共祖先（LCA）。虽然现在在线算法如倍增法（Binary Lifting）或基于RMQ的方法更为主流，但Tarjan的离线算法以其独特的思想和与并查集（Disjoint Set Union, DSU）的精妙结合。

5.1 底层原理

该算法将所有查询离线存储，然后通过一次DFS遍历整棵树来回答所有查询。其核心思想结合了DFS的回溯过程和并查集的集合合并功能。

数据结构：
- 一个并查集（DSU），用于维护已经访问过的节点所形成的子树森林。
- 一个 ancestor 数组，ancestor[i] 存储节点 $i$ 所在集合的“代表元”在DFS树中的祖先。在DSU中，这个代表元通常是子树的根。
- 一个 visited 数组，标记节点是否已被DFS完全探索（即已回溯）。
- 将查询 (u, v) 存储在 $u$ 和 $v$ 的邻接查询表中。
算法流程 tarjan_lca(u)：
1. 初始化：将 $u$ 自己的 ancestor 设为 $u$ 。
2. 递归访问子节点：对于 $u$ 的每个子节点 $v$ ，递归调用 tarjan_lca(v)。
3. 合并：当 tarjan_lca(v) 返回后，意味着 $v$ 的整个子树都已被探索完毕。此时，将 $v$ 所在的集合合并到 $u$ 所在的集合中（dsu.unite(u, v)），并更新新集合的 ancestor 为 $u$ 。
4. 处理查询：遍历所有与 $u$ $u$ 相关的查询 (u, q)。
  - 如果查询的另一端点 $q$ 已经被访问过 (visited[q] == true)，那么 $LCA(u, q)$ 就是 $q$ 所在集合的 ancestor，即 ancestor[dsu.find(q)]。
5. 标记完成：在 $u$ 的所有子树都处理完毕、所有相关查询都回答后，将 visited[u] 设为 true。

正确性解释：当算法在节点 $u$ 处处理查询 (u, q) 时，如果 $q$ 已经被访问，说明 $q$ 位于一个已经完全探索过的子树中。由于DFS的性质， $u$ 和 $q$ 的LCA，必定是 $u$ 的一个祖先（或者 $u$ 本身）。

考虑 $LCA(u, q) = lca$ 。当DFS从 $lca$ 向下走到 $u$ 的分支之前，它会先完成对 $q$ 所在分支的探索。当 dfs(q所在的子树) 完成并回溯到 $lca$ 时，q 所在的集合会被合并到 $lca$ 的集合中，并且这个新集合的 ancestor 被设置为 $lca$ 。

之后，DFS继续进行，最终到达 $u$ 。此时， $q$ 所在的集合的 ancestor 仍然是 $lca$ 。因此，当在 $u$ 处查询 (u, q) 时，通过 find(q) 找到 $q$ 所在集合的代表元，再取其 ancestor，得到的就是正确的LCA。

5.2 关键代码实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 500005;
vector<int> adj[N];
vector<pair<int, int>> qry[N]; 
int ans[N];
int p[N], anc[N]; 
bool vis[N];

int find(int x) {
    return p[x] == x ? x : p[x] = find(p[x]);
}

void unite(int x, int y, int new_anc) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        p[fy] = fx;
        anc[fx] = new_anc;
    }
}

void tj(int u, int fa) {
    p[u] = u;
    anc[u] = u;

    for (int v : adj[u]) {
        if (v == fa) continue;
        tj(v, u);
        unite(u, v, u); // 合并子树, 新祖先是u
    }

    vis[u] = true;

    for (auto& q : qry[u]) {
        int v = q.first;
        int id = q.second;
        if (vis[v]) {
            ans[id] = anc[find(v)];
        }
    }
}

void solve() {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        qry[u].push_back({v, i});
        qry[v].push_back({u, i});
    }

    tj(s, 0);

    for (int i = 0; i < m; ++i) {
        cout << ans[i] << "\n";
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

代码解析：
- qry[u] 存储了所有与节点 $u$ 相关的查询。
- p 是并查集的父指针数组，anc 是我们为每个集合维护的祖先。
- tj(u, fa) 是核心函数。
- unite 函数在合并集合时，将 fy 的根指向 fx，并将 fx 所在集合的 anc 更新为 new_anc (即当前的 $u$ )。
- 在 tj 函数中，对子节点递归完成后，立即将子节点集合合并到当前节点。
- vis[u] = true 语句的位置很关键，它必须在处理完所有子树和查询之后，标志着以 $u$ 为根的整个子树（包括 $u$ 本身）都已“尘埃落定”。
- 查询处理部分，if (vis[v]) 确保了只有当查询的另一端点 $v$ 所在的子树被完全处理后，才进行回答。
复杂度分析：
- 时间复杂度：每个节点和边被DFS访问一次。每个查询被处理两次。并查集的操作接近常数时间。总时间复杂度为 $O(N + M\alpha(N))$ ，其中 $N$ 是节点数， $M$ 是查询数， $\alpha$ 是反阿克曼函数。
- 空间复杂度：邻接表和查询表需要 $O(N+M)$ ，其余数组为 $O(N)$ ，总空间复杂度为 $O(N+M)$ 。

6. 应用四：2-SAT 问题

2-SAT（2-Satisfiability）问题是Tarjan算法在逻辑推理和约束满足问题中的一个强大应用。它利用SCC来高效地判断一组布尔变量是否存在满足所有约束的赋值。

6.1 问题定义

给定 $n$ 个布尔变量 $x_1, x_2, \dots, x_n$ 和 $m$ 个约束条件。每个约束条件的形式为 $(A \lor B)$ ，其中 $A$ 和 $B$ 是某个变量或其否定形式（例如 $x_i$ 或 $\neg x_i$ ）。问题是：是否存在一组对这些变量的真/假赋值，使得所有 $m$ 个约束条件都成立？

6.2 转化为图论问题

2-SAT问题的巧妙之处在于，可以将逻辑约束转化为图中的有向边（蕴含关系）。

一个逻辑或表达式 $(A \lor B)$ 等价于两个蕴含式：

$(\neg A \Rightarrow B)$ (如果A是假的，那么B必须是真的)
$(\neg B \Rightarrow A)$ (如果B是假的，那么A必须是真的)

我们可以为每个变量 $x_i$ 建立两个节点：

节点 $i$ 代表 $x_i$ 为真。
节点 $i+n$ 代表 $x_i$ 为假 (即 $\neg x_i$ 为真)。

于是，一个约束条件，例如 $(x_i \lor \neg x_j)$ ，就可以转化为两条有向边：

$\neg x_i \Rightarrow \neg x_j$ ：从代表 $\neg x_i$ 的节点 $i+n$ 向代表 $\neg x_j$ 的节点 $j+n$ 连边。
$x_j \Rightarrow x_i$ ：从代表 $x_j$ 的节点 $j$ 向代表 $x_i$ 的节点 $i$ 连边。

通过这种方式，我们可以将所有的 $m$ 个约束条件都转化为这个拥有 $2n$ 个节点和 $2m$ 条边的蕴含图。

6.3 基于SCC的判定

在构建好的蕴含图上，一条从节点 $u$ 到节点 $v$ 的路径意味着“选择 $u$ ” 蕴含了 “必须选择 $v$ ”。

问题的关键在于矛盾。什么样的赋值会导致矛盾？当一个变量 $x_i$ 既要为真，又要为假时，就产生了矛盾。在我们的图中，这对应于：

从节点 $i$ ( $x_i$ 为真) 出发，可以到达节点 $i+n$ ( $x_i$ 为假)。
同时，从节点 $i+n$ ( $x_i$ 为假) 出发，可以到达节点 $i$ ( $x_i$ 为真)。

这种情况，等价于节点 $i$ 和节点 $i+n$ 处在同一个强连通分量 (SCC) 中。

结论：一个2-SAT问题有解，当且仅当对于任何变量 $x_i$ ，其对应的节点 $i$ 和 $i+n$ 不在同一个SCC中。

我们可以用Tarjan算法求出蕴含图的所有SCC。然后，只需检查对所有的 $i \in [1, n]$ ，scc[i] 是否等于 scc[i+n]。如果存在任何一个 $i$ 满足此条件，则问题无解。

6.4 构造方案

如果问题有解，我们还需要给出一组具体的赋值方案。这可以通过缩点后SCC形成的DAG的拓扑序来完成。

在一个SCC内的所有节点，它们的真假性是捆绑的。如果我们选择其中一个节点为真，那么这个SCC内的所有其他节点也必须为真。

考虑缩点后的DAG。如果存在一条从SCC $A$ 到SCC $B$ 的边，那么选择 $A$ 就蕴含了选择 $B$ 。为了避免矛盾，我们应该优先满足拓扑序靠后的SCC的赋值。

一个简单的构造方法是：比较 scc[i] 和 scc[i+n] 的编号。Tarjan算法求出的SCC编号通常具有逆拓扑序的性质（即SCC的根出栈越晚，其拓扑序越靠前，编号越大）。

如果 scc[i] < scc[i+n]，意味着 scc[i+n] 的拓扑序更靠前。选择 $\neg x_i$ (节点 $i+n$ ) 比选择 $x_i$ (节点 $i$ ) 的“优先级”更高。我们赋值 $x_i$ 为假。
如果 scc[i] > scc[i+n]，则赋值 $x_i$ 为真。

这样赋值可以保证不会产生矛盾。

6.5 典型实例分析

例题: 洛谷 P4782 【模板】2-SAT 问题

题意概括

给定 $n$ 个布尔变量和 $m$ 个约束条件。每个条件形如 “变量 $x_i$ 为 $a$ 或变量 $x_j$ 为 $b$ ”，其中 $a, b \in \{0, 1\}$ 。要求给每个变量赋一个真值（0 或 1），使得所有 $m$ 个条件均被满足。如果存在这样的赋值，输出一种方案；否则，报告无解。

数据范围： $1 \le n, m \le 10^6$ 。

题目分析

本题是经典的 2-SAT (2-Satisfiability) 问题，可以通过构建 推导图 (Implication Graph) 并利用 Tarjan 算法 寻找 强连通分量 (Strongly Connected Components, SCC) 来解决。

2-SAT 建模：每个布尔变量 $x_i$ 有两种状态。我们建立一个包含 $2n$ 个节点的图。在此，我们做出关键约定：
- 节点 $i$ 代表 " $x_i$ 为 假 (0)"。
- 节点 $i+n$ 代表 " $x_i$ 为 真 (1)"。
构建推导图：一个约束条件 " $A$ 或 $B$ " 在逻辑上等价于两个蕴含式： "如果 $\neg A$ 那么 $B$ " ( $\neg A \Rightarrow B$ ) 和 "如果 $\neg B$ 那么 $A$ " ( $\neg B \Rightarrow A$ )。每个蕴含式 $P \Rightarrow Q$ 可以在图中表示为一条从代表 $P$ 的节点到代表 $Q$ 的节点的有向边。对于约束 “ $x_i$ 为 $a$ 或 $x_j$ 为 $b$ ”，我们添加两条边：
- 蕴含式一：如果 $x_i$ 不为 $a$ ，则 $x_j$ 必须为 $b$ 。对应的边为：从代表 x_i 不为 a 的节点 i+(1-a)*n 指向代表 x_j 为 b 的节点 j+b*n。
- 蕴含式二：如果 $x_j$ 不为 $b$ ，则 $x_i$ 必须为 $a$ 。对应的边为：从代表 x_j 不为 b 的节点 j+(1-b)*n 指向代表 x_i 为 a 的节点 i+a*n。
判定与求解：
- 判定无解：如果在构建的推导图中，某个变量 $x_i$ 所对应的两个节点（ $i$ 和 $i+n$ ）位于同一个强连通分量中，则问题无解。这意味着选择 $x_i$ 为假会导致 $x_i$ 必须为真，反之亦然，形成逻辑矛盾。
- 构造解：如果问题有解，我们可以通过比较一个变量的两个节点所在 SCC 的编号来赋值。Tarjan 算法找到 SCC 的顺序是图的拓扑排序的逆序，即 SCC 编号越小，其在拓扑序中越靠后。我们必须选择拓扑序更靠后的状态以避免推出矛盾。
  - 比较代表 $x_i$ 为假的节点 $i$ 和代表 $x_i$ 为真的节点 $i+n$ 。
  - 如果 $scc[i+n] < scc[i]$ ，说明“真”状态 ( $i+n$ ) 所在的 SCC 拓扑序更靠后，必须选择它，故 $x_i$ 赋值为 1。
  - 否则， $scc[i] < scc[i+n]$ ，说明“假”状态 ( $i$ ) 所在的 SCC 拓扑序更靠后，必须选择它，故 $x_i$ 赋值为 0。
  - 因此，最终 $x_i$ 的值为表达式 (scc[i+n] < scc[i]) 的结果。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAX = 2e6 + 5;

int n, m;
vector<int> g[MAX];       // 邻接表
int dfn[MAX], low[MAX], ts; // Tarjan 算法时间戳
int stk[MAX], top;        // Tarjan 算法的栈
bool ins[MAX];            // 节点是否在栈内
int scc[MAX], cnt;        // SCC 编号和计数

void tj(int u) {
    dfn[u] = low[u] = ++ts;
    stk[++top] = u;
    ins[u] = true;

    for (int v : g[u]) {
        if (!dfn[v]) {
            tj(v);
            low[u] = min(low[u], low[v]);
        } else if (ins[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        ++cnt;
        int v;
        do {
            v = stk[top--];
            ins[v] = false;
            scc[v] = cnt;
        } while (v != u);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    for (int k = 0; k < m; ++k) {
        int i, a, j, b;
        cin >> i >> a >> j >> b;
        // 节点 i 代表 x_i=0, 节点 i+n 代表 x_i=1
        // 约束 (x_i=a or x_j=b) 转换为两个蕴含式
        // (x_i != a) => (x_j = b)
        // (x_j != b) => (x_i = a)
        // x_k=v 对应的节点是 k+v*n
        // x_k!=v 对应的节点是 k+(1-v)*n
        g[i + (1 - a) * n].push_back(j + b * n);
        g[j + (1 - b) * n].push_back(i + a * n);
    }

    for (int i = 1; i <= 2 * n; ++i) {
        if (!dfn[i]) {
            tj(i);
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (scc[i] == scc[i + n]) {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }

    cout << "POSSIBLE\n";
    for (int i = 1; i <= n; ++i) {
        // scc 编号越小, 拓扑序越靠后, 必须选择该状态
        // scc[i] 是 x_i=0 的 scc 编号
        // scc[i+n] 是 x_i=1 的 scc 编号
        // 若 scc[i+n] < scc[i], 则 x_i 赋值为 1, 否则为 0
        cout << (scc[i + n] < scc[i]) << " ";
    }
    cout << "\n";

    return 0;
}

7. 回头再看

回顾本文所讨论的Tarjan算法的各种应用——强连通分量、割点与桥、双连通分量、离线LCA、2-SAT——可以发现，它们都构建在同一个坚实的基础上：深度优先搜索树的结构特性，以及通过 $dfn$ 和 $low$ 两个数组对返祖边和横叉边所形成的回环路径进行的量化分析。

$dfn$ 提供了时间的参照系，而 $low$ 则捕捉了图中节点“向上爬”的能力。正是 $dfn$ 与 $low$ 之间的大小关系，成为了揭示图连通性奥秘的关键钥匙。

$dfn[u] == low[u]$ 在有向图中定义了SCC的根。
$low[v] > dfn[u]$ 在无向图中标识出唯一的“桥梁”。
$low[v] \ge dfn[u]$ 在无向图中定位了连接的“枢纽”——割点。

掌握了这一核心思想，就能在面对新的图论问题时，思考是否能通过类似的DFS框架来解决。

附录

A.1 最少加边使有向图强连通

这是一个在算法竞赛中频繁出现的经典问题，被誉为强连通分量 (SCC) 的“黄金应用”。

问题描述： 给定一个有向图 G，至少需要添加多少条有向边，才能使整个图变为强连通图？
解决方案：
1. 缩点： 首先，利用 Tarjan 算法求出原图 G 中所有的强连通分量 (SCC)。然后，将每个 SCC 视为一个单一的节点，构建一个新的有向无环图 (DAG)。如果原图中存在一条从 SCC A 到 SCC B 的边，那么在新图中就连接一条从 A 指向 B 的边。
2. 分析 DAG： 在这个缩点后的 DAG 中，统计所有入度为 0 的点的数量，记为 S；统计所有出度为 0 的点的数量，记为 T。
3. 计算答案： 所需添加的最少边数为 max(S, T)。这个结论的直观理解是，我们需要从“终点”（出度为0的SCC）连接到“起点”（入度为0的SCC），以形成一个大的环路结构，从而贯通整个图。当 S 和 T 不相等时，通过巧妙地连接，总可以用 max(S, T) 条边将所有的起点和终点串联起来。
4. 特殊情况： 如果原图本身已经是一个强连通图，那么缩点后只有一个节点，此时 S 和 T 均为 0（或按定义为1，但图中无边），答案为 0。

A.2 最少加边使无向图点双连通（V-BCC 增广）

与 E-BCC（边双连通分量）的增广问题相似，V-BCC（点双连通分量）也有对应的加边问题，其解决方法通常依赖于一种被称为“圆方树”的优美数据结构。

问题描述： 给定一个无向图 G，至少需要添加多少条边，才能使整个图变为点双连通图？
解决方案：
1. 构建圆方树 (Block-Cut Tree)：
  - 首先利用 Tarjan 算法找出图中所有的点双连通分量 (V-BCC) 和割点。
  - 我们创建两种类型的节点：“圆点”代表原图中的顶点，“方点”代表每一个 V-BCC。
  - 对于每一个 V-BCC，让其对应的方点向该 V-BCC 中包含的所有圆点（即原图顶点）连边。
  - 这样构造出的新图是一棵树（或森林），即为圆方树。
2. 分析圆方树： 在构建好的圆方树上，如果一个方点所代表的 V-BCC 在树中是叶子节点（即只与一个割点相连，度数为1），我们称之为一个“叶子块”。
3. 计算答案： 统计圆方树中叶子块的个数，记为 L。所需添加的最少边数为 ceil(L / 2)，即 L 除以 2 向上取整。其思想是通过在不同的叶子块之间加边，将它们“捆绑”起来，消除割点，最终形成一个大的点双连通分量。

A.3 桥树/圆方树 + LCA 做路径类查询

将图结构转化为树结构是解决图上路径问题的常用技巧。Tarjan 算法帮助我们构建的桥树和圆方树，结合最近公共祖先 (LCA) 等树上算法，能高效处理复杂的路径查询。

场景一：查询两点路径上经过多少条桥？
- 方法： 首先用 Tarjan 算法找出所有的桥。然后，将每个边双连通分量 (E-BCC) 缩成一个点，桥则成为连接这些新点的树边，从而构成一棵“桥树”。
- 查询： 任意两点 u, v 之间的路径问题，就转化为了桥树上对应节点之间的路径问题。查询路径上的桥数量，等价于计算桥树上两点路径的长度（边数）。这可以通过 LCA 算法快速求解。
场景二：查询两点路径上有多少个割点？
- 方法： 构建原图的圆方树。在圆方树中，原图中的割点是连接不同“方点”（V-BCC）的“圆点”。
- 查询： 查询原图中两点 u, v 之间简单路径上的割点集合，等价于查询圆方树上 u, v 两点路径上经过的所有圆点（不含 u, v 本身）。同样，可以利用 LCA 算法定位路径，然后进行统计。

A.4 Johnson 算法枚举有向图所有简单环

在某些复杂分析中，我们需要找出图中所有的简单环（不含重复节点的环）。Johnson 算法是解决该问题的经典方法，而 Tarjan 算法在其中扮演了关键的预处理角色。

核心思想： 一个简单环内的所有顶点必定属于同一个强连通分量 (SCC)。因为在一个环上，任意两点都可以互相到达。
算法流程：
1. 分解图： 利用 Tarjan 算法将原图分解为若干个强连通分量。
2. 分治处理： 对每一个 SCC 子图，独立地使用 Johnson 的环查找算法来枚举其中所有的简单环。
3. 合并结果： 将所有 SCC 中找到的环合并起来，即为原图中所有的简单环。

通过首先将图分解为 SCC，Johnson 算法有效地将一个大问题分解为若干个互不相干的小问题，极大地“缩小了搜索范围”，提升效率。