Tarjan算法是用于求图上的强连通分量(环)的算法。
应用：
强连通是有向图才有的概念。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。求有向图的强连通分量是Tarjan最基本的应用。
算法原理：
Tarjan算法的复杂度是O(v+e)的，因为只需要进行一次dfs就能处理出一个块中所有的强连通分量。首先建立dfn[]数组和low[]数组，前者记录节点的dfs序(第几个被dfs到)，确定后就不会改变，后者记录该节点属于的强连通分量中dfs序最小的节点(的dfs序)，是会不断更新的。申明一个栈，用于存储可能成为强连通分量中的点。
然后，依次对每个节点进行dfs(因为从一个节点不一定能遍历到其他所有的节点)，初始化low[]为dfs序(low[u]=dfn[u]=dfsid)，将每次dfs的点u加入栈中，遍历这个点能到达的相邻的点v，如果这个点在栈中，说明构成了一个环，也就是强连通分量，就用v点的dfs序更新(取min)low[u]，当递归回溯时，所有强连通分量中的点low[]值都会被更新为dfn[v]。当一个点u的low[]值与它的dfs序相同时，说明这个点是一个强连通分量的根(也可能这个分量只有这一个点)，将栈中的点逐个弹出，直至u(也弹出)为止，将这些点染成同个颜色。
缩点：对于有些有向图上的问题，可以将一个强连通分量用一个点来等效替代，这个时候染成的一种颜色就是新图上的一个点。
int vis[maxn];//记录栈中的元素
int cnt[maxn];//记录一个强连通分量中的结点个数
int color[maxn];//染色，将同一个强连通分量中的点染成同个颜色
int dfn[maxn],low[maxn],dfsid=0,id=0;
stack<int>st;
void tarjan(int u){
low[u]=dfn[u]=++dfsid;
vis[u]=1;
st.push(u);
for(int i=head[u];i>0;i=E[i].next){
int v=E[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){//u是一个强连通分量的根
id++;
int k;
do{
k=st.top();st.pop();
vis[k]=0;
color[k]=id;
cnt[id]++;
}while(k!=u);
}
}
int main(){
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
}割点是无向图才有的概念。如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割集。若一个割集只有一个点，则称这个点为割点。
算法原理：
设u为dfs中的非根结点，如果点u的子结点v(后遍历到的点)能遍历到的最小 dfs序>=dfn[u]，那么删除u后v将和u之前的点断开，说明u是割点 。虽然是无向图，但这里的遍历是有方向的，一个点不能沿着已经访问过的点继续往前(根)遍历，但是low[]值能被所有相邻点更新。最后得到的low[]并不是正确的(能访问到的最小dfs序)，因为后续结点被限制在只能遍历到已访问过的点就停止了，因此判断的时候用low[v]==dfn[u]其实也是可以的。
若u是dfs中的根结点，那么如果u有2个及以上的儿子(除去u之外的每个连通块都是一个儿子)，u是割点。
set<int>res;
void tarjan(int u,int rt){
low[u]=dfn[u]=++dfsid;
int child=0;
for(int i=head[u];i>0;i=E[i].next){
int v=E[i].to;
if(!dfn[v]){
child++;
tarjan(v,rt);
low[u]=min(low[u],low[v]);
if(u!=rt&&low[v]>=dfn[u])
res.insert(u);
}
low[u]=min(low[u],dfn[v]);
}
if(u==rt&&child>1)
res.insert(u);
}
int main(){
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i,i);
}原文：https://www.cnblogs.com/ucprer/p/11586773.html