蒟蒻刚学Tarjan有一个弱智问题(轻喷)
查看原帖
蒟蒻刚学Tarjan有一个弱智问题(轻喷)
983702
lrj3247楼主2024/7/24 10:29

我看很多题解的代码,就拿第一篇大佬的代码举例

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???(轻喷)

2024/7/24 10:29
加载中...