rt,这是一个普通的强连通分量代码:
void tarjan(int x)
{
dfn[x]=low[x]=++cnt,st[++top]=x,k[x]=1;
for(register int i=0;i<v[x].size();i++)
if(!dfn[v[x][i]]) tarjan(v[x][i]),low[x]=min(low[x],low[v[x][i]]);
else if(k[v[x][i]]) low[x]=min(low[x],dfn[v[x][i]]);
if(dfn[x]==low[x])
{
ans++;
while(st[top+1]!=x)
k[st[top]]=0,col[st[top--]]=ans;
}
}
在循环中,如果点 v[x][i] 所在的强连通分量已经处理完,就不用它来更新 low[x]。可是 low[x] 的定义不是 x 所能到达的最远节点吗,不知道是哪里理解出了问题,求解答!