关于割点判定法则在程序实现上的疑问
  • 板块学术版
  • 楼主Forg1weN
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/10/12 20:54
  • 上次更新2023/11/2 14:14:33
查看原帖
关于割点判定法则在程序实现上的疑问
225515
Forg1weN楼主2023/10/12 20:54

如下是一份割点判定法则的代码

void tarjan(int x,int fa) {
    int son=0;
    dfn[x]=low[x]=++num;
    Q[++top]=x;
    for(int i=hd[x];i;i=edge[i].nt) {
        int y=edge[i].v;
        if(!dfn[y]) {
            son++;
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]) {//here
                ++tot;
                v_dcc[tot].push_back(x);
                int z;
                do {
                    z=Q[top--];
                    v_dcc[tot].push_back(z);
                }while(z!=y);
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
    if(fa==0 && son==0)v_dcc[++tot].push_back(x);
}

在注释语句,若把 ≥\ge 改成 == ,在任何求 tarjan 的题目都不会有正确性区别,但是与蓝书上的判定法则不符,请问两者的区别在哪里?

2023/10/12 20:54
加载中...