C++中的塔尖算法（Tarjan算法）詳解

一、什么是Tarjan算法？

Tarjan算法是一種由Robert Tarjan提出的高效圖論算法，主要用于求解有向圖的強連通分量（Strongly Connected Components, SCC）。該算法基于深度優先搜索（DFS），能夠在線性時間內完成這一任務，時間復雜度為$O(n+m)$，其中$n$是頂點數，$m$是邊數。其核心思想是通過維護一個棧和兩個關鍵數組（dfn和low）來識別圖中的所有強連通分量。

二、算法原理與實現步驟

1. 核心概念

• dfn[u]：記錄節點$u$被訪問的順序編號（時間戳）。
• low[u]：表示從節點$u$出發能追溯到的最早棧中節點的時間戳。
• 棧結構：用于存儲當前路徑上的節點，幫助判斷哪些節點屬于同一個強連通分量。

2. 主要邏輯

以下是算法的關鍵步驟：

1. 初始化：對每個未訪問過的節點調用tarjan(u)函數。
   • 設置dfn[u] = low[u] = ++index，并將節點壓入棧中。
2. 遍歷鄰接點：對于每個鄰接點$v$：
   • 如果$v$未被訪問過，則遞歸調用tarjan(v)，然后更新low[u] = min(low[u], low[v])。
   • 如果$v$已在棧中（即處于當前搜索路徑上），則用dfn[v]更新low[u]。
3. 判斷根節點：當dfn[u] == low[u]時，說明找到了一個強連通分量的根節點。此時將棧中從該節點開始的所有元素彈出，這些節點構成一個完整的SCC。

3. C++代碼示例

#include <iostream>
#include <vector>
#include <stack>
using namespace std;const int MAXN = 1e5 + 5; // 根據實際需求調整大小
vector<int> g[MAXN];      // 鄰接表存圖
int dfn[MAXN], low[MAXN], color[MAXN]; // dfn/low數組及所屬顏色標記
bool inStack[MAXN];       // 標記是否在棧內
stack<int> stk;           // 輔助棧
int timestamp = 0;        // 全局時間戳
int sccCount = 0;         // 強連通分量計數器void tarjan(int u) {dfn[u] = low[u] = ++timestamp; // 初始化時間戳stk.push(u);inStack[u] = true;for (auto v : g[u]) {if (!dfn[v]) {          // 未訪問過tarjan(v);low[u] = min(low[u], low[v]); // 更新low值} else if (inStack[v]) {         // v在棧中，屬于當前路徑low[u] = min(low[u], dfn[v]); // 用dfn更新low}}// 如果u是某個SCC的根節點if (dfn[u] == low[u]) {++sccCount;                        // 新增一個SCCwhile (true) {int x = stk.top();stk.pop();inStack[x] = false;             // 移出棧并標記color[x] = sccCount;            // 染色分類if (x == u) break;              // 直到彈出u為止}}
}int main() {int n, m;cin >> n >> m;                         // 輸入點數和邊數for (int i = 0; i < m; ++i) {int a, b;cin >> a >> b;                     // 添加有向邊a→bg[a].push_back(b);}// 對所有未訪問節點執行Tarjan算法for (int i = 1; i <= n; ++i) {if (!dfn[i]) {tarjan(i);}}// 輸出結果：每個節點所屬的SCC編號for (int i = 1; i <= n; ++i) {cout << "點" << i << "屬于第" << color[i] << "個SCC" << endl;}return 0;
}

三、應用場景與擴展

1. 典型應用

• 縮點優化：將每個SCC視為單個超級節點，構建新的有向無環圖（DAG），便于后續處理如拓撲排序、最長路徑等問題。
• 雙連通分量檢測：稍作修改后可用于尋找無向圖中的橋和割點。
• 競賽題目：許多圖論問題通過縮點轉化為更簡單的形式，例如動態規劃或貪心策略的應用。

2. 注意事項

• 多次調用的處理：確保每次DFS前清空相關狀態變量（如vis數組）。
• 內存管理：對于大規模數據，建議使用動態分配而非靜態全局數組。
• 邊界條件：注意自環邊和重復邊的處理方式。

四、為什么選擇Tarjan算法？

相較于其他方法（如Kosaraju算法），Tarjan算法的優勢在于：

• 單次DFS完成所有工作，無需額外反向建圖；
• 空間效率高，僅需常數額外空間維護棧和標記數組；
• 易于擴展，支持多種變體以適應不同場景需求。

五、總結

Tarjan算法作為圖論中的經典算法之一，其高效性和靈活性使其成為解決強連通分量相關問題的首選工具。通過深入理解其原理并結合實踐編碼，你可以更輕松地應對復雜的圖結構分析任務。無論是競賽編程還是實際工程應用，掌握這一算法都將顯著提升你的解題能力！