Tarjan 模板
因为每次写Tarjan都会写挂，所以整理了一些模板。主要的证明就跳过了，主要区分不同模板的差异。
有向图和无向图
有向图和无向图的实现有时候会有区别，因为建出DFS树之后，有向图可能有横叉边，但是无向图不会（显然），所以有些细节需要注意。而且无向图判重边会比较麻烦。
无向图
void Tarjan(int u,int rt){
dfn[u]=low[u]=++num;
st.push(u);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
Tarjan(v,rt);
low[u]=min(low[u],low[v]);
}
else low[u]=min(low[u],dfn[v]);
}
}
有向图
void Tarjan(int u,int rt){
dfn[u]=low[u]=++num;
st.push(u);
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
Tarjan(v,rt);
low[u]=min(low[u],low[v]);
}
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
}
可以看到，有向图较无向图只多了一个vis记录某节点是否在栈中，因为在栈中的节点都是当前节点在DFS树上的祖先节点，这样可以排除横叉边干扰。
割点/点双连通分量（无向图）
cut表示割点，scc表示点双包含的元素。一个点可以属于多个点双。（实际上只有割点可以）
求割点和点双本质上是一样的，判断条件：$ low[v]=dfn[u] $
网上存在两种写法，详见代码。
void Tarjan(int u,int rt){
dfn[u]=low[u]=++tot;
st.push(u);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
son[u]++;
Tarjan(v,rt);
low[u]=min(low[u],low[v]);
if(low[v]==dfn[u]){//也可写成low[v]>=dfn[u]，但是需要下一行的特判
cut[u]=1;//if(u!=rt||son[u]>1)cut[u]=1;
num++;int k=0;
do{
k=st.top();
scc[num].push_back(k);
st.pop();
}while(k!=v);
scc[num].push_back(u);//当前节点也在点双中
}
}
else low[u]=min(low[u],dfn[v]);
}
}
割边/边双连通分量/强连通分量（无向图）
brige表示割边，dcc表示边双包含的元素。每个点只会属于一个边双。
相似求法，判断条件：$ low[v]<dfn[u] $
与割点几乎没有区别。唯一不好的是重边容易出错，原因？
由于是无向图，所以直接由父亲节点更新当前节点的low是不正确的，有重边例外。一个可行的实现是：记录一个vis为这条边是否遍历过，只能有未经过的边转移。（一个技巧，初始化cnt（链式前向星的边数）为1，这样 \(i\) 和 \(i\ xor \ 1\) 就对应同一条边 ）
void Tarjan(int u,int rt,int fa){
dfn[u]=low[u]=++tot;
st.push(u);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
vis[i]=vis[i^1]=1;
Tarjan(v,rt,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]){
brige[e[i].id]=1;
num++;
int k=0;
do{
k=st.top();
dcc[num].push_back(k);
st.pop();
}while(k!=v);
}
}
else if(!vis[i]) low[u]=min(low[u],dfn[v]);
}
// if(dfn[u]==low[u]){
// ans++;
// int k=0;
// do{
// k=st.top();
// dcc[ans].push_back(k);
// st.pop();
// }while(k!=u);
// }
// 求边双也可以写成这样，便于和缩点一起记忆
}
缩点（有向图）
缩点就是把一个强连通分量缩成一个点，使原图成为一个DAG。
void Tarjan(int u,int rt){
dfn[u]=low[u]=++tot;
st.push(u);
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
Tarjan(v,rt);
low[u]=min(low[u],low[v]);
}
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
int k=0;num++;
do{
k=st.top();
scc[num].push_back(k);
vis[k]=0;//注意清空vis
bel[k]=num;
sum[num]+=val[k];
st.pop();
}while(k!=u);
}
}
总结
我写过的差不多就这些，主体部分是相似的（也许这是为什么Tarjan总学不会），重点区分点双和边双的判断条件，有向图和无向图的处理细节。对于不同的写法记一种就够用了。