Tarjan 算法是一种高效的求有向图中所有强连通分量的方法。一个强连通分量（SCC）是一个极大子图，其中任意两个顶点之间都是可达的。
概念
强连通
在图论中，强连通通常用于描述有向图的性质。一个有向图被称为强连通的，如果对于图中的任意两个顶点 u 和 v，都有一条从 u 到 vv 的路径，以及一条从 v 到 u 的路径。这意味着在强连通的图中，任意两个顶点都可以互相到达。
强连通分量
强连通分量（Strongly Connected Component，简称 SCC）是有向图中的一个重要概念。强连通分量是图的一个子集，它满足以下两个条件：
- 强连通性：该子图中的任意两个顶点 u 和 v 都满足有从 u 到 v 的路径，以及从 v 到 u 的路径。
- 极大性：这个子集是极大的，即不能再增加其他顶点而仍然保持强连通性。如果将其中的一个顶点去掉，子集将不再是强连通的。
换句话说，强连通分量是一个最大化的强连通子图。如果考虑一个有向图，它可能由多个强连通分量组成。每个强连通分量都是一个独立的部分，且其中的每一个顶点都可以互相到达。
缩点
在图论中，缩点（also known as contracting a graph or condensation of a graph）是将图中的强连通分量（SCCs）视为单个节点，从而将原图简化为一个DAG（有向无环图）的过程。这对于许多算法和图论问题来说是一个重要的步骤，特别是在分析有向图的结构时。缩点的过程：
- 寻找强连通分量（SCCs）：使用Tarjan算法或Kosaraju算法找到图中的所有强连通分量。
- 创建新图：每个强连通分量作为新图中的一个节点。
- 添加边：如果原图中有从一个强连通分量到另一个强连通分量的边，那么在新图中添加对应的边。
Tarjan算法
算法思想
- 深度优先搜索 (DFS): 算法对图进行深度优先搜索（DFS）。
- 索引和低值: 为每个节点分配一个唯一的索引，并维护一个低值数组，表示该节点或其子节点能够回溯到的最小索引。
- 栈: 使用栈来存储当前路径上的节点，且这些节点尚未确定其所在的强连通分量。
- 回溯: 在DFS过程中，如果发现一个节点能够回溯到自身或其祖先，则表明找到一个强连通分量。
步骤
- 对每个未访问的节点，执行DFS。
- 在DFS过程中，为当前节点分配索引和低值，并将其压入栈中。
- 遍历当前节点的邻接节点，对于每一个邻接节点：
- 如果未被访问，递归执行DFS，并更新当前节点的低值。
- 如果在栈中，更新当前节点的低值。
- 如果当前节点的低值等于其索引，则从栈中弹出所有节点直到当前节点，形成一个强连通分量。
算法模板
#include <bits/stdc++.h>
using namespace std;vector<vector<int>> tarjan(const vector<vector<int>> &graph) {const int n = graph.size();vector<vector<int>> SCCS; // 存储所有强连通分量vector<int> dfn(n, -1), low(n); // dfn 用于记录节点的访问顺序，low 用于记录最小可达节点vector<bool> insta(n, false); // 记录栈中是否存在该节点stack<int> sta; // 存储当前的 DFS 栈int time = 0; // 时间戳function<void(int)> dfs = [&](int x) {sta.push(x);insta[x] = true;dfn[x] = low[x] = time++;for (int y : graph[x]) {if (dfn[y] == -1) { // y 还未被访问dfs(y);low[x] = min(low[x], low[y]);} else if (insta[y]) { // y 在栈中，说明是一个回边low[x] = min(low[x], dfn[y]);}}// 如果 x 是一个强连通分量的根节点if (dfn[x] == low[x]) {vector<int> component; // 当前强连通分量while (true) {int node = sta.top();sta.pop();insta[node] = false; // 从栈中移除component.push_back(node); // 加入当前强连通分量if (node == x) break; // 如果到达根节点，则结束}SCCS.push_back(component); // 将当前强连通分量加入结果}};// 遍历每个节点，进行 DFSfor (int i = 0; i < n; ++i) {if (dfn[i] == -1) { // 仅在未访问的节点上调用 DFSdfs(i);}}return SCCS;
}vector<vector<int>> condenseGraph(const vector<vector<int>> &graph, const vector<vector<int>> &sccs) {unordered_map<int, int> scc_map; // 记录每个节点所属的强连通分量索引// 遍历所有强连通分量，将每个节点映射到其对应的强连通分量索引for (int i = 0; i < sccs.size(); ++i) {for (int node : sccs[i]) {scc_map[node] = i;}}// 创建一个新的图，用于存储缩点后的结果vector<unordered_set<int>> condensed_graph(sccs.size());// 遍历原图中的每个节点及其邻居节点for (int v = 0; v < graph.size(); ++v) {for (int w : graph[v]) {// 如果两个节点不在同一个强连通分量中，则在新图中添加一条边if (scc_map[v] != scc_map[w]) {condensed_graph[scc_map[v]].insert(scc_map[w]);}}}// 将 unordered_set 转换为 vector，以便返回结果vector<vector<int>> result(condensed_graph.size());for (int i = 0; i < condensed_graph.size(); ++i) {result[i].assign(condensed_graph[i].begin(), condensed_graph[i].end());}return result; // 返回缩点后的图
}
例题
B3609 图论与代数结构 701] 强连通分量
给定一张 n 个点 m 条边的有向图，求出其所有的强连通分量。第一行一个整数表示这张图的强连通分量数目。接下来每行输出一个强连通分量。
#include <bits/stdc++.h>
using namespace std;vector<vector<int>> tarjan(const vector<vector<int>> &graph);int main(){int n,m;cin>>n>>m;vector<vector<int>> G(n);for(int i=0;i<m;i++){int u,v;cin>>u>>v;--u,--v;if(u==v)continue;G[u].push_back(v);}auto sccs=tarjan(G);unordered_map<int, int> scc_map;for (int i = 0; i < sccs.size(); ++i) for (int node : sccs[i]) scc_map[node] = i;vector<bool> vis(sccs.size());cout<<sccs.size()<<endl;for(int i=0;i<n;i++){if(vis[scc_map[i]])continue;vis[scc_map[i]]=true;auto& scc=sccs[scc_map[i]];sort(scc.begin(),scc.end());for(int i:scc)cout<<i+1<<' ';cout<<endl;}return 0;
}
