在tarjan算法中,有的教材上写了直接检测是否是根,也就只有一个点的强连通分量。要记得出栈,不然如果再次搜到这个点,它的时间戳会影响正常搜索。
void tarjan(int x)
{
dfn[x]=low[x]=++tot;
s.push(x);ins[x]=1;
if(x==root&&g[x].size()==0) {s.pop();ins[x]=0;cnt++;scc[x]=cnt;return;}
for(int i=0;i<g[x].size();i++)
{
int y=g[x][i];
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y]) low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x])
{
int z;cnt++;
do
{
z=s.top();
s.pop();
scc[z]=cnt;
ins[z]=0;
}while(z!=x);
}
}