Tarjan算法详解
参考文章：强连通分量
Tarjan算法是一种用于寻找有向图中强联通分量（Strongly Connected Components, SCCs）的算法。它是由Robert Tarjan在1972年提出的，基于深度优先搜索（DFS）和栈的数据结构。
基本概念
- 强联通分量：在一个有向图中，如果一组节点中任意两个节点都可以互相到达，那么这组节点就构成了一个强联通分量。
- DFS序：在深度优先搜索过程中，每个节点被访问的顺序。
- low值：一个节点的low值表示该节点通过一条后向边或交叉边能够到达的最小DFS序的节点。
算法步骤
-
初始化：
- 对每个节点初始化
dfn（DFS序）和low值。 - 使用一个栈来记录当前路径上的节点。
- 初始化一个计数器
idx来记录DFS序。
- 对每个节点初始化
-
深度优先搜索：
- 从任意一个未访问的节点开始进行DFS。
- 访问到一个节点
u时，设置dfn[u]和low[u]为当前的idx值，并将u入栈。 - 遍历
u的所有邻接节点v：- 如果
v未被访问过，则递归访问v，并在递归返回后更新low[u]为min(low[u], low[v])。 - 如果
v在栈中，则更新low[u]为min(low[u], dfn[v])。
- 如果
-
发现强联通分量：
- 当
dfn[u]等于low[u]时，说明从u开始的路径形成了一个强联通分量。 - 从栈中弹出节点，直到弹出
u为止，这些节点构成一个强联通分量。
- 当
伪代码
function tarjan(u):
dfn[u] = low[u] = ++idx
stack.push(u)
for each v in adj[u]:
if v is not visited:
tarjan(v)
low[u] = min(low[u], low[v])
else if v in stack:
low[u] = min(low[u], dfn[v])
if dfn[u] == low[u]:
while true:
v = stack.pop()
// 处理强联通分量
if v == u:
break
题目：强连通分量
代码详解
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010; // 定义常量N，表示图中节点的最大数量
vector<int> g[N]; // 邻接表存储图
int dfn[N], low[N], ins[N], idx; // 定义数组和变量
// dfn[u] 表示节点u的DFS序
// low[u] 表示节点u所在的子树中能跳到的最小DFN，且未被切掉，即ins[v]=true
// ins[u] 表示节点u是否在栈中
// idx 为当前遍历序列号
int bel[N], cnt; // bel[u] 表示节点u在哪个强联通分量里，cnt表示强联通分量的数量
int n, m; // n表示节点数，m表示边数
stack<int> stk; // 栈，用于存储当前路径上的节点
vector<vector<int>> ans; // 存储所有强联通分量
// Tarjan算法求强联通分量
void tarjan(int u) {
dfn[u] = low[u] = ++idx; // 初始化dfn和low
ins[u] = true; // 标记节点u在栈中
stk.push(u); // 将节点u入栈
// 遍历节点u的所有邻接节点
for (auto v : g[u]) {
if (!dfn[v]) { // 如果节点v未访问过
tarjan(v); // 递归访问节点v
low[u] = min(low[u], low[v]); // 更新low[u]
} else if (ins[v]) { // 如果节点v在栈中
low[u] = min(low[u], dfn[v]); // 更新low[u]
}
}
// 如果dfn[u] == low[u]，说明找到了一个强联通分量
if (dfn[u] == low[u]) {
cnt++; // 强联通分量数量加1
vector<int> c; // 存储当前强联通分量的节点
while (true) {
int v = stk.top(); // 取出栈顶节点
stk.pop(); // 弹出栈顶节点
bel[v] = cnt; // 标记节点v属于当前强联通分量
c.push_back(v); // 将节点v加入当前强联通分量
ins[v] = false; // 标记节点v不在栈中
if (v == u) break; // 如果栈顶节点是u，结束循环
}
sort(c.begin(), c.end()); // 对当前强联通分量的节点排序
ans.push_back(c); // 将当前强联通分量加入结果
}
}
signed main() {
cin >> n >> m; // 输入节点数和边数
for (int i = 1; i <= m; i++) { // 输入每条边
int u, v;
cin >> u >> v;
g[u].push_back(v); // 添加边到邻接表
}
for (int i = 1; i <= n; i++) { // 对每个未访问的节点进行Tarjan算法
if (!dfn[i]) tarjan(i);
}
cout << cnt << endl; // 输出强联通分量的数量
sort(ans.begin(), ans.end()); // 对所有强联通分量排序
for (auto c : ans) { // 输出每个强联通分量的节点
for (auto i : c) {
cout << i << " ";
}
cout << endl;
}
}
简化版：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010;
vector<int> g[N];
int dfn[N],low[N],ins[N],idx;
int bel[N],cnt;
//ins[u]表示u这个结点是否在栈里面
//low[u]表示u这个结点所在的子树里面能跳到的DFN最小，且未被切掉，即ins[v]=true;
//dfn[u]表示u这个结点的DFS序
//idx为当前遍历序列号
//bel[u]表示u在哪个强联通分量里
int n,m;
stack<int> stk;
vector<vector<int> >ans;
void tarjan(int u)
{
dfn[u]=low[u]=++idx;
ins[u]=true;
stk.push(u);
for(auto v : g[u])
{
if(!dfn[v]) tarjan(v);
if(ins[v]) low[u]=min(low[u],low[v]);
}
if(dfn[u]==low[u])
{
cnt++;
vector<int> c;
while(true){
int v=stk.top();
stk.pop();
bel[v]=cnt;
c.push_back(v);
ins[v]=false;
if(v==u) break;
}
sort(c.begin(),c.end());
ans.push_back(c);
}
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i]) tarjan(i);
}
cout<<cnt<<endl;
sort(ans.begin(),ans.end());
for(auto c : ans){
for(auto i : c)
{
cout<<i<<" ";
}
cout<<endl;
}
}