求解割点疑问
  • 板块学术版
  • 楼主int8
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/7/5 22:54
  • 上次更新2024/7/6 10:06:08
查看原帖
求解割点疑问
551089
int8楼主2024/7/5 22:54

为什么这样写全WA

void tarjan(int u,int fa){
    dfn[u]=low[u]=++tot;
    int ch=0;
    for(auto v:g[u]){
        if(fa==v) continue;
        if(!dfn[v]){
            ch++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }
        else low[u]=min(low[u],dfn[v]);
        if(u!=root&&low[v]>=dfn[u]) gedian[u]=1;  //这里
    }
    if(u==root&&ch>1) gedian[root]=1;
    return ;
}

而这样写AC

void tarjan(int u,int fa){
    dfn[u]=low[u]=++tot;
    int ch=0;
    for(auto v:g[u]){
        if(fa==v) continue;
        if(!dfn[v]){
            ch++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(u!=root&&low[v]>=dfn[u]) gedian[u]=1;  //这里
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(u==root&&ch>1) gedian[root]=1;
    return ;
}

能说明一下或者给一个hack数据吗

2024/7/5 22:54
加载中...