· 区别于有向图(他的儿子是可能等于他的爸爸的)所以需要这么打
tarjan(1,0);
void tarjan(int x,int fa)
{
dfn[x]=low[x]=++tot;
q.push(x),ins[x]=1;
for(int y:e[x])
if(y==fa) continue;//他的儿子是可能等于他的爸爸的
else if(!dfn[y])
tarjan(y,x),low[x]=min(low[x],low[y]);
else if(ins[y])
low[x]=min(low[x],dfn[y]);
if(dfn[x]==low[x])
{
int y;++cnt;
while(y!=x)
y=q.top(),
q.pop(),
ins[y]=0,
color[y]=cnt;
}
}
标签:tarjan,int,无向,ins,dfn,low,cnt
From: https://www.cnblogs.com/Charlieljk/p/17865959.html