求解强联通分量 tarjan算法

xiaoxiao2021-02-28  90

自己总结一下:dfn就是 时间戳 而low 是还在 栈中的最小时间戳,low相等的都在同一个联通分量

else if(v[e[i].v])//v 是vis 为true 代表该点还在栈中 low[now]=min(low[now],dfn[e[i].v]); //这里用dfn 是因为 这是第二次访问该点,也就是说 是可以通过该点进行强连通的,而low[e[i].v] 是不一定的,可能在另一个强连通分量中没有出栈,栈里面不只有一个强连通分量

转载请注明原文地址: https://www.6miu.com/read-26616.html

最新回复(0)