tarjan具体思想与代码模版

Tarjan算法是一种经典的深度优先搜索（DFS）为基础的强连通分量（Strongly Connected Components, SCCs）检测算法。其基本思想是将图视为一个有向无环图（DAG），通过寻找从任意节点开始的最深路径来确定每个节点所属的强连通分量。它主要包含以下几个步骤：

1. 初始化：设置每个节点的低点和父节点为自身，同时初始化发现时间和终结时间（DFSTime和LowLink）为0，以及一个数组S（标记集合）和栈F（辅助栈）。

2. 遍历图：对每个未访问过的节点，从根节点开始做DFS。如果遇到一个节点v，将其入栈F，然后递归地遍历所有v的前驱节点，更新lowlink值。

3. 虚拟节点：在v的前驱节点全部访问完毕后，如果v的lowlink等于DFSTime(v)，说明找到了一个SCC，此时会创建一个新的SCC，并将该节点添加到当前SCC的集合S中。接着跳过v的所有后续节点，它们已经在更低的时间层。

4. 检查循环：对于每个节点u，若u不在S中，但在F栈上，则表示存在循环，此时从u开始，继续查找下一个可达的节点，直到找到低点等于当前节点的节点，这样就形成了一个循环。

5. 更新：当遍历完一个SCC后，更新剩余节点的lowlink和DFSTime。

以下是简单的C++代码模板（假设`adjList`是一个邻接表表示的图，`addEdge(u, v)`用于添加边）：

void tarjan(int u, int& dfsTime, vector<int>& lowLink, vector<vector<int>>& adjList) {
    dfsTime[u] = lowLink[u] = ++dfsTime;
    stack<int> F;
    F.push(u);
    while (!F.empty()) {
        u = F.top(); F.pop();
        if (lowLink[u] != dfsTime[u]) continue;
        int sccId = dfsTime[u];
        for (int v : adjList[u]) {
            if (dfsTime[v] == -1) {
                tarjan(v, dfsTime, lowLink, adjList);
                lowLink[u] = min(lowLink[u], lowLink[v]);
            } else if (v != parent[u]) {
                lowLink[u] = min(lowLink[u], dfsTime[v]);
            }
        }
        if (lowLink[u] == dfsTime[u]) {
            // 新的强连通分量
            vector<int> scc;
            do {
                scc.push_back(u);
                u = F.top(); F.pop();
            } while (u != v);
            sccId++;
            for (int x : scc) {
                parent[x] = sccId; // 更新父节点标识
            }
        }
    }
}

// 初始化
vector<int> parent(numNodes), lowLink(numNodes, -1);
for (int i = 0; i < numNodes; ++i) dfsTime[i] = -1;

这里的`parent`数组记录了每个节点的父节点，`lowLink`数组记录了每个节点的最低可达节点ID。