对于判断根节点是否为割点
一些博客上写的是:根必须保证有至少两个儿子节点
所以代码就是
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那种是正确的?