想问一下为什么这样改也能AC
查看原帖
想问一下为什么这样改也能AC
274886
daijuruo楼主2020/10/26 12:16
void tarjan(int x){
        dfn[x]=low[x]=++tot;
        s.push(x);insta[x]=true;//节点x在栈中
        for(int i=head[x];i;i=edge[i].next)
        {//通过对u点上一个边序的挂钩构造对连接u点的所有边数遍历查找对应v点
            int u=edge[i].to;
            if(!dfn[u])
            {//如果没访问过
                tarjan(u);//往下进行延伸,开始递归
                low[x]=min(low[x],low[u]);//根据定义x能到u,所以low[]取两者最小(更早的那个)
            }
            else if(insta[u])low[x]=min(low[x],dfn[u]);//如果访问过了,取min直接用时间戳
        }

最后一行改成if(insta[u])low[x]=min(low[x],low[u]); 居然也过了,是数据太水了吗,顺便想问下为啥不能这么写,没太想明白,谢谢大佬。

2020/10/26 12:16
加载中...