蒟蒻求助关于tarjan求割点中对于根节点的判断
  • 板块学术版
  • 楼主_8762
  • 当前回复16
  • 已保存回复16
  • 发布时间2021/11/10 21:45
  • 上次更新2023/11/4 00:55:55
查看原帖
蒟蒻求助关于tarjan求割点中对于根节点的判断
370829
_8762楼主2021/11/10 21:45

对于判断根节点是否为割点

一些博客上写的是:根必须保证有至少两个儿子节点

所以代码就是

inline void tarjan(int x,int root){
  low[x]=dfn[x]=++dfstime;
  int child=0;
  for(int i=head[x];i;i=nxt[i]){
    int y=ver[i];
    if(!dfn[y]){
      tarjan(y,root);
      low[x]=min(low[x],low[y]);
      if(low[y]>=dfn[x]&&x!=root) cut[x]=1;
      if(x==root) child++;
    }
    low[x]=min(low[x],dfn[y]);
  }
  if(child>=2) cut[x]=1;
}

但是还有一些博客上写:

若根是割点,当且仅当根至少有两个子结点满足

low[x]>=dfn[y]

void tarjan(int u){
    dfn[u]=low[u]=++dfstime;
    int flag=0;
    for(int i=head[u];i;i=nxt[i]){
	int v=ver[i];
	if(!dfn[v]){
	    tarjan(v);
	    low[u]=min(low[u],low[v]);
	    if(low[v]>=dfn[u]){
		flag++;
		if(u!=root||flag>1) cut[u]=1;
	    }
	}
	else low[u]=min(low[u],dfn[v]);
    }
}

这两份代码感觉区别挺大的,尤其是一个在

if(low[v]>=dfn[u])里判断一个不是,但是都过了模板题

所以问问各路dalao那种是正确的?

2021/11/10 21:45
加载中...