浅谈Tarjan
干啥的
Tarjan是用来求强连通分量的算法
有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。
是不是看不懂？举个栗子
这个图中的强连通分量有。
tarjan算法的过程大概就是DFS，上代码！
cpp
void tarjan(int x){//
low[x]=dfn[x]=++depth;
vis[x]=1;
q.push(x);
Graph(i,x)
if(!dfn[e[i].v])tarjan(e[i].v),low[x]=min(low[x],low[e[i].v]);
else if(vis[e[i].v])low[x]=min(low[x],low[e[i].v]);
if(dfn[x]==low[x])
while(y=q.top()){//缩点main(找到了强连通分量，加入一个点中)
q.pop();
sd[y]=x;
vis[y]=0;
if(x==y)break;
a[x]+=a[y];
}
}
有啥用
1.缩点
有时候在一张图上出现了环，于是很多事情变得不太方便会卡死，这时候缩点就很有必要了，你可以把一个有环的图变成有向无环图。
用上面的图举个例子吧
缩点前
缩点后
这个点6就包括了点1，2，3。
2.割点
在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。 如果某个割点集合只含有一个顶点X（也即{X}是一个割点集合），那么X称为一个割点。
就是说这个点删除后强连通块增加了，那么这个点就是割点，如图，点1即为割点
怎么求割点呢？
其实和之前强连通分量中的tarjan差不多了，如果这个点的dfn比low要小，说明他的子树中没有能够到达他祖先的点，他是这个双连通分量的一个割点，但要加一个特判，根节点如果有两个及以上的儿子，那么他也是割点。