void tarjan(int x,int fa) {
dfn[x]=low[x]=++cnt;
vis[x]=1;
int son=0;
for(int i=head[x]; ~i; i=ne[i]) {
int v=to[i];
if(vis[v]) {
if(v!=fa) {
low[x]=min(low[x],dfn[v]);
}
continue;
}
tarjan(v,x);
son++;
if(low[v]>=dfn[x]&&x!=1)key[x]=1;
low[x]=min(low[x],low[v]);
}
if(x==1&&son>=2)key[x]=1;
}
疑问:既然这里是在处理后向边,那low[x]不应该变成low[x]=min(low[x],low[v]);吗?子节点能够到达的最小编号不就是父亲能到达的最小编号吗?
改成low[x]=min(low[x],low[v]);为什么会错?
求教,悬赏关注。