Tarjan算法，是以一位计算机界大佬的名字命名的算法，多用于解决LCA，割点，强连通分量等问题，下面是其发明者的简短介绍。

Robert Tarjan，计算机科学家，以LCA、强连通分量等算法闻名。他拥有丰富的商业工作经验，1985年开始任教于普林斯顿大学。

切入正题，我们先来看一下tarjan算法的第一个主要用途：求强连通分量。

1.强连通分量

什么是强连通分量呢？

有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。

通俗一点来说，就是假设有A,B,C三个点，他们之间存在一些线路，使得两两之间直接或间接连接，若在图中属于最多点间的强连通系统，那么这样的一个整体称之为强连通分量。

我们来看一下这个算法的思路：

定义三个必需的数组和一个必需的全局变量：作为“时间戳”的sequence[amount]数组，记录当前点可以回溯到达的最靠向根节点的一个点的数组lowest_reach[amount],和记录当前点是否在栈中的vis[amount]数组，以及记录当前点的current_turn。如不用STL的话，还可以定义一个模拟栈stacks[amount]，和与之配套的指针top，最好由邻接表（链式前向星）存储图。从给定的根节点出发，一个枝一个枝地搜索这个数据树，用vis[current_turn]=1标记在栈中的数据，并以当前点为起点，沿着邻接表已经记录好的路线一直搜寻，若下一个点没有被访问，则直接递归进行更深层的搜索，不然直接将当前点的lowest_reach和这条路下一个点的lowest_reach取最小值。驱逐在栈中的且已被判定的强连通分量。

实现代码：

int current_turn=0,top=0;int secquence[360],stacks[360],lowest_reach[360];bool vis[360];///necessary preparation for tarjanstruct node{int next,to}nodes[360];int heads[360];void tarjan(int current){secquence[current]=lowest_reach[current]=++current_turn;stacks[top++]=current;vis[current]=1;for(int heads[current];i!=-1;i=nodes[i].next){int toward=nodes[i].to;if(secquence[towrad]==0){tarjan(toward);lowest_reach[current]=min(lowest_reach[current],lowest_reach[toward]);}else lowest_reach[current]=min(lowest_reach[current],lowest_reach[toward]);///the other opinion says it should be secquence[toward]if(secquence[current]==lowest_reach[current]){vis[current]=false;while(stacks[top--]!=current){vis[stacks[top--]]=false; } top--;}

2.割点

看一下割点的定义。

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。

如果某个割点集合只含有一个顶点X（也即{X}是一个割点集合），那么X称为一个割点。

连通分量指的是若干点间各自互相有直接或者间接联系的系统，这里所说的“增多”可以说是把原图一分为多。也就是说，割点就是，这个点的存在维系着两侧图是否可以连通。

那么我们如何求出这些割点呢？仍然是tarjan算法，但是和上边相比有一些改动。

我们看一下改动后的思路：

仍然是用sequence数组记录访问次序，lowest_reach记录可以回溯到的最靠近根节点的点，这里的vis数组将直接标记割点，整个过程不需要栈，但需要一个根节点号，和一个用来记录根节点子树的变量child。按着邻接表所存储的路线向深处搜索。当我们搜索完下一个结点时，发现访问次序sequence小于等于下一个点的lowest_reach,若等于，则意味着下一个点至少不能回到当前点，也就是说不连通，标记当前点。同时若current_turn回到了根节点，那说明某个线路与根节点是连通的。此时child++,若根节点有两棵及以上的子树，则可以判定这个根节点也是割点。

实现代码：

int current_turn=0,child=0;int secquence[360],lowest_reach[360];bool vis[360];struct node{int next,to}nodes[360];int heads[360];void tarjan(int current,int root){secquence[current]=lowest_reach[current]=++current_turn;child=0;for(int heads[current];i!=-1;i=nodes[i].next){int toward=nodes[i].to;if(secquence[towrad]==0){tarjan(toward);lowest_reach[current]=min(lowest_reach[current],lowest_reach[toward]);if(lowest_reach[current]>=sequence[current]&&current!=rootvis[current]=1;if(current==root)child++;}else lowest_reach[current]=min(lowest_reach[current],lowest_reach[toward]);}if(child>=2&&current==root)vis[current]=1; }