关于 Tarjan 求割点
  • 板块学术版
  • 楼主Terraria
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/11/4 14:08
  • 上次更新2023/11/4 01:28:05
查看原帖
关于 Tarjan 求割点
289275
Terraria楼主2021/11/4 14:08

有几个很大的疑惑,希望得到解决/kk

  • 对于如下代码:
void tarjan(int x){
    dfn[x]=low[x]=(++cnt);
    int child=0;
    for(int i=0;i<edge[x].size();i++){
        int y=edge[x][i];
        if(!dfn[y]){
            child++;
            fa[y]=x;
            tarjan(y);
            if(fa[x]==-1&&child>=2) ans[x]=1;
            if(fa[x]!=-1&&low[y]>=dfn[x]) ans[x]=1;
            low[x]=min(low[x],low[y]);
        }
        else if(y!=fa[x]){
            low[x]=min(low[x],dfn[y]);
        }
    }
}

为什么将这份代码改为

int child=0;
void tarjan(int x){
    dfn[x]=low[x]=(++cnt);
    child=0;
    for(int i=0;i<edge[x].size();i++){
        int y=edge[x][i];
        if(!dfn[y]){
            child++;
            fa[y]=x;
            tarjan(y);
            if(fa[x]==-1&&child>=2) ans[x]=1;
            if(fa[x]!=-1&&low[y]>=dfn[x]) ans[x]=1;
            low[x]=min(low[x],low[y]);
        }
        else if(y!=fa[x]){
            low[x]=min(low[x],dfn[y]);
        }
    }
}

时会是错的(详见 P3388 中我的提交记录挂掉了 #11:)

  • 对于 P3388,题目中有说

tarjan图不一定联通。

那我是不是可以构造出一组数据:

4 1
1 2

这样子得到的图是 1-2 3 4,那这样子不就应该每个点都是割点了吗?

也就是对于这组数据,肉眼可知输出应该是

4
1 2 3 4

但是,经测试,第一页的所有题解全部输出 0

如果这个构造符合要求的话,那是不是意味着有大批题解出了问题呢?

2021/11/4 14:08
加载中...