作为弱者，寒假讲tarjan的时候就没懂，yyr对我说，tarjan很简单，tarjan很重要，一定要学…我心里虚，tarjan明明那么难的…（害怕），然后今天看了一下，卧槽这么简单…真的好容易理解啊…我以前是有多弱…
所以对于看了SHHHS博客的朋友来说，我把SHHHS的Tarjan自己敲了一遍，然后给了注释
是这样
void Tarjan(int x){ dfn[x]=++dfs_num;//访问到dfn,dfn为时间戳++; low[x]=dfs_num;//初始化能追溯到的在栈中的最早的祖先是自己; vis[x]=true;//是否在栈中; stack[++top]=x;//自己入栈; for(int i=head[x];i!=0;i=e[i].next){ int temp=e[i].to; if(!dfn[temp]){//如果该点没有被访问过 Tarjan(temp);//就以它为根访问他的子树 low[x]=gmin(low[x],low[temp]);//访问结束后,用x孩子的low来更新x的low } else if(vis[temp])low[x]=gmin(low[x],dfn[temp]);//如果该孩子已经被访问过,则用该孩子的序号去更新x的low,这样一来就可以处理叶子部分(x)有一条边连向上面部分的情况 } //处理完所有x的情况之后(遍历完所有x的子点后) if(dfn[x]==low[x]){//构成强连通分量 vis[x]=false; color[x]=++col_num;//染色,将该强连通分量染成col_num的颜色 while(stack[top]!=x){//清空,最底层是x color[stack[top]]=col_num; vis[stack[top--]]=false; } top--; } }