这里给出一个dalao炒鸡详细的解释：
https://www.cnblogs.com/stxy-ferryman/p/7779347.html#4073877
Tarjan算法
void Tarjan(
int u)
{
dfn[u]=low[u]=++
num;
vis[u]=
1;
st[++top]=u;
//入栈
for(
int i=h[u];i;i=
e[i].next)
{
int v=
e[i].to;
if(!
dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
//low表示u与其子孙到达的最小编号
}
else
if(vis[v])
//判断v是否在栈中
{
low[u]=
min(low[u],dfn[v]);
//可以改成 min(low[u],low[v])
//因为此时v的low和dfn还未修改
}
}
if(dfn[u]==
low[u])
{
col++
;
while(st[top+
1]!=
u)
{
co[st[top]]=col;
//属于第col个强连通分量
vis[st[top--]]=
0;
}
}
}
View Code
可用于缩点求在DAG上问题
转载于:https://www.cnblogs.com/BrokenString/p/9688440.html
