请问为什么在tarjan中,把判定割点的if写到if(!dfn[v])
中是正确的,而写到外面是错的呢?
代码:
void tarjan(int u){
dfn[u]=low[u]=++SEQ;
int son=0;
for(int i=f[u];i;i=edge[i].next){
int v=edge[i].v;
if(!dfn[v]){
son++;
tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]&&u^root) ans.insert(u);
}
else low[u]=min(low[u],dfn[v]);
}
if(u==root&&son>1) ans.insert(u);
}
中的
if(low[v]>=dfn[u]&&u^root) ans.insert(u);
这句,写成
void tarjan(int u){
dfn[u]=low[u]=++SEQ;
int son=0;
for(int i=f[u];i;i=edge[i].next){
int v=edge[i].v;
if(!dfn[v]){
son++;
tarjan(v);
low[u]=min(low[u],low[v]);
}
else low[u]=min(low[u],dfn[v]);
if(low[v]>=dfn[u]&&u^root) ans.insert(u);
}
if(u==root&&son>1) ans.insert(u);
}
就错了。
蒟蒻觉得,就算把这句放到if外面,点v没有进入 if(!dfn[v]) ,那么点v应该就是以前搜到过的。所以low[v]应当小于dfn[u],也就记录不到ans里,不会对答案有影响...但是为什么放外面会0分,放里面就AC了