C++怎么实现一个Tarjan算法求强连通分量_C++图论高级算法与DFS应用

尼克 2025-11-24 00:00:00 次阅读

Tarjan算法通过DFS遍历和时间戳求有向图的强连通分量，利用dfn和low数组确定SCC根节点，配合栈结构实现O(V+E)时间复杂度的高效求解。

在有向图中，强连通分量（Strongly Connected Component, SCC）是指图中任意两个顶点都能互相到达的最大子图。Tarjan算法是一种基于深度优先搜索（DFS）的高效算法，能够在O(V + E)的时间复杂度内求出所有强连通分量。

算法核心思想

Tarjan算法利用了DFS的遍历顺序和时间戳来识别强连通分量。每个节点维护两个值：

dfn[u]：节点u被访问的时间戳
low[u]：以u为根的搜索子树中，能通过后向边或横叉边到达的最小时间戳

当递归回溯时，如果发现dfn[u] == low[u]，说明u是一个强连通分量的“根”，此时栈中从u开始的所有节点构成一个SCC。

实现步骤与代码结构

以下是C++实现Tarjan算法的关键步骤：

初始化全局时间戳、dfn数组、low数组、标记是否在栈中的数组
对每个未访问的节点启动DFS
在DFS过程中更新dfn和low，并将节点压入栈
回溯时更新父节点的low值
若dfn[u] == low[u]，则弹出栈中元素直到u，这些节点构成一个SCC

#include 
#include 
#include 
using namespace std;

const int MAXN = 1e5 + 5;
vector graph[MAXN];
int dfn[MAXN], low[MAXN], timestamp = 0;
bool inStack[MAXN];
stack st;
vector> sccs;

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    st.push(u);
    inStack[u] = true;

    for (int v : graph[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 (dfn[u] == low[u]) {
        vector scc;
        while (true) {
            int top = st.top();
            st.pop();
            inStack[top] = false;
            scc.push_back(top);
            if (top == u) break;
        }
        sccs.push_back(scc);
    }
}

int main() {
    int n, m;
    cin >> n >> m;

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

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

    cout << "Found " << sccs.size() << " SCC(s):\n";
    for (int i = 0; i < sccs.size(); i++) {
        cout << "SCC " << i + 1 << ": ";
        for (int node : sccs[i]) {
            cout << node << " ";
        }
        cout << "\n";
    }

    return 0;
}