我看很多题解的代码,就拿第一篇大佬的代码举例
struct edge{
int x,y,w;
}E[maxm];
int dfn[maxn],low[maxn],tmmk=0;
bool v[maxn];//v数组用来跟踪这个点是否已经处理完毕,我们稍后会见到它的用法
stack<int> S;
void tarjan(int x)
{
dfn[x]=low[x]=++tmmk;//每个点在最开始被访问时,时间戳和low值都是一样的
S.push(x);
v[x]=true;
for(int i=head[x];i;i=next[i])//链式前向星查邻接点
{
int y=E[i].y;//不熟悉的同学请像这样打多一点,有助于理解
if(!dfn[y])//dfn的初值都是0,如果这个点没有搜过,就递归搜索
{
tarjan(y);
low[x]=min(low[x],low[y]);//此时搜索已经回溯,我们可以确定y的low值已经更正,所以用它来更新x的
}//因为y在x的后面,所以y能访问到的祖先x一定可以访问到
else
if(v[y])//如果y点搜过了且在栈里,说明我们找到了 后!向!边!
low[x]=min(low[x],dfn[y]);
}//但是此时我们还不能急着处理,为什么?因为有回溯到根了以后我们在收集到了完整的信息
if(dfn[x]==low[x])
{//dfn和low一样,你就是与众不同的根节点
ans++;//ans是强连通分量的个数
int y;
do{
y=S.top();
S.pop();
v[y]=false;//为什么要将这里改成false??????????????????????
col[y]=ans;//y点属于编号为ans的强连通分量
g[ans].push_back(y);//存下每个强连通分量的成员
}while(y!=x)//在这里将栈里的点全部倒出来(倒垃圾一样..)
}
}
为什么出栈的时候要将v[y]改成false???(轻喷)