CC++ & Algorithm

强连通分量——Tarjan算法

较难2
语言版本：C++
概述：Tarjan算法像一个大力士，能把有向图中互相能到达的“好朋友小组”揪出来。

强连通分量与Tarjan算法：把有向图中的“好朋友小组”一网打尽

想象一下，在一个有向图中，顶点就像班级里的同学，有向边就像“单向认识”的关系。如果A能通过一条条边走到B，同时B也能沿着某些边走回A，那么A和B就是“互相认识”的，我们称它们强连通。把一群互相都能到达的顶点聚在一起，就形成了一个强连通分量（SCC）——就像班级里的几个“好朋友小组”，组内每个人都能通过朋友介绍互相认识。

Tarjan算法就像一位侦探，用一次深度优先搜索就能找出图中所有的SCC。它由计算机科学家Robert Tarjan发明，特别高效。接下来我们就一起揭开它的秘密。

1. 基础概念：什么是强连通分量？

强连通：在有向图里，如果顶点u和v之间既能从u走到v，又能从v走到u，就说u和v是强连通的。

强连通分量：一个最大的顶点集合，其中任意两个顶点都是强连通的。注意“最大”这个词，意思是不能再往里面加别的顶点而仍然保持这个性质。比如下面这个图：

  • 顶点0 → 1 → 2 → 0 形成了一个环，它们仨就是强连通的。
  • 顶点1还能到3，3到4，但4不能回到3或1，所以3和4各自是单独的SCC（或者3和4不互相连通，则各自为一种）。

生活中的例子：在微信群里，如果每个人都能通过@或者转发接触到群里的每个人，这个群就是一个强连通分量。但如果有人只能看不能发言，那他就不是其中的一份子。

2. Tarjan算法的核心思想

Tarjan算法只做一次DFS（深度优先搜索），给每个顶点记下两个时间戳：

  • dfn[u]（discovery time）：顶点u被第一次访问到的顺序（从1开始编号）。
  • low[u]（lowest link）：从u出发，通过DFS树上的边和一条返祖边（即回边），能追溯到的最小的dfn值。通俗地说，就是u能“拐弯抹角”回到的最早的那个祖先是什么顺序。

算法借助一个栈，每访问一个新顶点，就把它压入栈里。当DFS回溯时，如果发现某个顶点u的 low[u] == dfn[u]，说明u是它所在SCC的“根”（或者叫“老大”），于是从栈顶弹出u以及u之后入栈的所有顶点，它们就构成了一个SCC。

比喻：地下迷宫探险

你在地下迷宫探险，每到一个新路口就掏出一个记号笔写上自己到达的顺序号（这就是dfn）。同时，你在心里默默记下：从当前路口能通过哪些通道（包括走过的回头路）回到的最小顺序号（这就是low）。如果有一天你发现自己能回到自己的起始记号，说明你找到了一个环，环里所有的路口就是一个SCC。这时候，你从入口处的栈里把这一圈路口全部取出来，就算找到了一个SCC。

3. 算法步骤详解（配代码）

下面是完整代码，我们先逐步拆解关键部分。

3.1 所需的数据结构

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAXN = 100;                     // 最大顶点数
vector<int> adj[MAXN];                    // 邻接表存图
int dfn[MAXN], low[MAXN];                // dfn[u]=访问顺序, low[u]=能追溯到的最早顺序
int dfs_clock = 0;                       // 全局时间戳（从1开始）
bool inStack[MAXN];                      // 标记顶点是否在栈中
stack<int> stk;                          // 栈，用于存放当前正在处理的顶点
vector<vector<int>> sccs;                // 存放所有强连通分量，每个分量是一个vector

3.2 核心函数 tarjan(u)

void tarjan(int u) {
    low[u] = dfn[u] = ++dfs_clock;       // 1. 设置u的dfn和low，都等于当前时间戳
    stk.push(u);                         // 2. 将u压入栈
    inStack[u] = true;                   // 3. 标记u在栈中
    
    // 4. 遍历u的所有邻居v
    for (int v : adj[u]) {
        if (!dfn[v]) {                   // 情况A：v还没被访问过
            tarjan(v);                   //   递归处理v
            low[u] = min(low[u], low[v]);//   更新u的low为：u原来的low和v的low的最小值
        } else if (inStack[v]) {         // 情况B：v已经访问过且还在栈中（说明是返祖边）
            low[u] = min(low[u], dfn[v]);//   更新u的low：取u的low和v的dfn的最小值
        }
        // 情况C：v已访问过且不在栈中，说明v属于其他SCC，忽略即可
    }
    
    // 5. 如果low[u] == dfn[u]，说明u是SCC的根，弹栈得到这个SCC
    if (low[u] == dfn[u]) {
        vector<int> scc;                 // 用来存这个SCC里的所有顶点
        while (true) {
            int x = stk.top(); stk.pop();// 弹出栈顶
            inStack[x] = false;          // 标记已出栈
            scc.push_back(x);            // 加入SCC
            if (x == u) break;           // 弹出到u时停止（因为u是根）
        }
        sccs.push_back(scc);             // 把这个SCC存到总结果中
    }
}

为什么low[u]==dfn[u]意味着找到了一个SCC？

想象一下：low[u]是u能通过DFS树和返祖边回到的最小dfn。如果low[u]等于dfn[u]，说明u不能回到任何比它更早的祖先（除了自己）。那么从u出发的所有能到达的、在栈中的顶点（即u的子孙们）都不能逃出u的控制范围——它们只能和u一起形成一个“圈”，也就是一个SCC。所以从栈里u之后的所有顶点都属于这个SCC。

3.3 主函数中的调用

int main() {
    int n = 5; // 顶点数
    // 添加有向边，构造一个示例图
    adj[0].push_back(1);
    adj[1].push_back(2);
    adj[2].push_back(0);   // 0-1-2 形成一个环，这就是一个SCC
    adj[1].push_back(3);
    adj[3].push_back(4);   // 3能到4，但4不能回到3，所以3和4各自是单独的SCC

    // 对每个未被访问的顶点调用tarjan（保证图可能不连通）
    for (int i = 0; i < n; ++i) {
        if (!dfn[i]) tarjan(i);
    }

    cout << "找到" << sccs.size() << "个强连通分量:\n";
    for (auto& scc : sccs) {
        for (int v : scc) cout << v << " ";
        cout << "\n";
    }
    return 0;
}

运行结果应该是：

找到3个强连通分量:
4
3
0 1 2

注意顺序：因为DFS顺序的原因，先处理3和4（从顶点0开始先走到1，然后2，回溯后再走1->3->4），所以先找到包含4的分量，然后是3，最后是0,1,2的环。

4. 新手容易犯的几个错误

错误1：忘记标记 inStack

如果忘了在出栈时 inStack[x]=false，或者忘了在入栈时设true，那么条件 else if (inStack[v]) 就会失效，导致错误地认为某些边是返祖边，从而更新low错误，最终可能把不属于同个SCC的顶点混在一起。

错误2：更新low时用了dfn[v]和low[v]混淆

  • 当v未访问时，递归返回后应该用 low[v] 更新 low[u]，因为v的low信息已经包含了它能回到的更早祖先。
  • 当v已访问且在栈中时，只能用 dfn[v]（而不是 low[v]）更新，因为此时v是u的祖先（可能是不同分支），用dfn才能保证只考虑返祖边。

记住口诀：“未访用low，在栈用dfn”。

错误3：图不连通时只从0号顶点开始DFS

如果图不连通，只从一个顶点开始DFS会遗漏其他连通分量。所以主函数中应该像代码那样，循环所有顶点，对未访问过的顶点单独调用tarjan。

错误4：用错栈顶判断

在弹栈得到SCC时，条件 if (x == u) break; 必须放在添加x之后，否则会把u漏掉。另外要注意栈是后进先出的，但SCC内部顶点顺序不重要。

5. 完整可运行示例（带更多顶点）

下面这个例子模拟一个班级里的“朋友圈”：

  • 0号同学认识1号
  • 1号认识2号，2号认识3号，3号认识1号（形成一个环）
  • 2号还认识4号
  • 4号认识5号，5号认识4号（另一个环）
  • 6号谁也不认识（单独一个人）
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
int dfn[MAXN], low[MAXN], dfs_clock = 0;
bool inStack[MAXN];
stack<int> stk;
vector<vector<int>> sccs;

void tarjan(int u) {
    low[u] = dfn[u] = ++dfs_clock;
    stk.push(u);
    inStack[u] = true;
    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        vector<int> scc;
        while (true) {
            int x = stk.top(); stk.pop();
            inStack[x] = false;
            scc.push_back(x);
            if (x == u) break;
        }
        sccs.push_back(scc);
    }
}

int main() {
    int n = 7;
    // 构建有向边
    adj[0].push_back(1);
    adj[1].push_back(2);
    adj[2].push_back(3);
    adj[3].push_back(1);   // 环1：1-2-3-1
    adj[2].push_back(4);
    adj[4].push_back(5);
    adj[5].push_back(4);   // 环2：4-5-4
    // 6号没有出边，是孤立顶点

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

    cout << "共有 " << sccs.size() << " 个强连通分量:\n";
    for (int i = 0; i < sccs.size(); ++i) {
        cout << "分量" << i+1 << ": ";
        for (int v : sccs[i]) cout << v << " ";
        cout << "\n";
    }
    return 0;
}

输出：

共有 4 个强连通分量:
分量1: 6
分量2: 5 4
分量3: 3 2 1
分量4: 0

注意：0号虽然能到1，但1不能回0，所以0单独一个SCC；6号孤立也单独。而1,2,3形成一个，4,5形成一个。

6. 相关知识点指引

学完Tarjan算法后，你可能会对以下内容感兴趣：

  • 缩点（Kosaraju算法）：另一种求SCC的算法，需要两次DFS，但思想更直观。
  • 缩点与DAG：把每个SCC缩成一个“超级顶点”，原图就变成了一个有向无环图（DAG），很多问题（如求最长路、拓扑排序）在DAG上就简单多了。
  • 割点与桥：类似的思想可以用于无向图，找出删除后会让图不连通的顶点（割点）或边（桥）。
  • 2-SAT问题：用强连通分量解决逻辑约束问题，比如“每个人要么选A要么选B，并且不能同时选冲突项”。

Tarjan算法不仅快，而且巧妙——用一个栈和两个数组就解决了问题。下次你在有向图里找“好朋友小组”时，就用它吧！

例题精讲

1单选题

Tarjan算法中，数组dfn[u]和low[u]的含义分别是什么？

Adfn[u]表示节点u的访问顺序编号，low[u]表示从u出发能到达的最早祖先的dfn值
Bdfn[u]表示节点u的深度，low[u]表示u所在强连通分量的根节点编号
Cdfn[u]表示节点u的访问顺序编号，low[u]表示从u出发能到达的最近兄弟的dfn值
Ddfn[u]表示节点u的深度，low[u]表示从u出发能到达的最早祖先的深度
2单选题

在Tarjan算法中，当访问到节点u，遍历其所有邻接边v时，若v尚未访问，则递归处理v后应如何更新low[u]？

Alow[u]=min(low[u], dfn[v])
Blow[u]=min(low[u], low[v])
Clow[u]=min(low[u], dfn[u])
Dlow[u]=max(low[u], low[v])
3判断题

Tarjan算法中，如果存在一条从节点u到节点v的边，且v已经在栈中，那么low[u]应更新为min(low[u], low[v])。

4判断题

Tarjan算法的时间复杂度是O(n+m)，其中n为节点数，m为边数。

5填空题
以下Tarjan算法代码片段中，在计算完low[u]后，如果dfn[u] == low[u]，则开始弹出栈中节点直到u，并记录强连通分量。请补全缺失的代码。
```cpp
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
vector<int> scc[N];
int scc_cnt;

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;
    for (int 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], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int y;
        do {
            y = stk[top--];
            in_stk[y] = false;
            scc[scc_cnt].push_back(y);
        } while (___);
    }
}