- 2022tysc1451 的博客
割点与桥
- 2025-8-21 9:53:07 @
void tarjan(int u,int fa){
int child=0;
dfn[u]=low[u]=++cnt;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v==fa)continue;//访问到已访问过的节点
if(dfn[v]==0){
child++;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])flag[u]=true;//为割点,标记
}else low[u]=min(low[u],dfn[v]);
}
if(fa==-1&&child==1)flag[u]=false;//为根节点标记为否
}