有几个很大的疑惑,希望得到解决/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:)?
tarjan图不一定联通。
那我是不是可以构造出一组数据:
4 1
1 2
这样子得到的图是 1-2 3 4
,那这样子不就应该每个点都是割点了吗?
也就是对于这组数据,肉眼可知输出应该是
4
1 2 3 4
但是,经测试,第一页的所有题解全部输出 0
。
如果这个构造符合要求的话,那是不是意味着有大批题解出了问题呢?