- 2022tysc0158 的博客
【模板】 Tarjan 缩点
- 2023-11-14 21:27:17 @
void tarjan(int u,int fa){
int child=0;
dfn[u]=low[u]=++tot;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(!dfn[v]){
child++;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])iscp[u]=true;
}else if(v!=fa)low[u]=min(low[u],dfn[v]);
}
if(fa<0&&child==1)iscp[u]=false;
}