思考算法讲完了，代码也写了，但是并没有结束，仍然有一个很大的疑惑没有解开 。算法的原理很简单，很容易学会，但问题是为什么这样做就是正确的呢？这其中的原理是什么呢？我们似乎仍然没有弄得非常清楚 。
这里面的原理其实很简单，我们来思考一下，如果我们在正向dfs的时候，u点出现在了v点的后面，也就是u点后于v点出栈 。有两种可能，一种可能是u点可以连通到v点，说明u是v的上游 。还有一种可能是u不能连通到v，说明图被分割成了多个部分 。对于第二种情况我们先不考虑，因为这时候u和v一定不在一个连通分量里 。对于第一种情况，u是v的上游，说明u可以连通到v 。
这时候，我们将图反向，如果我们从u还可以访问到v，那说明了什么？很明显，说明了在正向图当中v也有一条路径连向u，不然反向之后u怎么连通到v呢？所以，u和v显然是一个强连通分量当中的一个部分 。我们再把这个结论推广，所有u可以访问到的，第一次遍历时在它之前出栈的点，都在一个强连通分量当中 。
如果你能理解了这一点，那么整个算法对你来说也就豁然开朗了，相信剩下的细节也都不足为虑了 。
今天的文章到这里就结束了，如果喜欢本文的话，请来一波素质三连，给我一点支持吧（关注、转发、点赞） 。
- END -
本文始发于公众号：TechFlow，求个关注
推荐阅读
- SQL Server2000安装步骤详细介绍解读新人也会装了
- 金骏眉冲泡要点先容,金骏眉茶叶冲泡的步骤是怎样的
- 金骏眉茶叶的价格介绍,金骏眉茶叶冲泡的步骤是怎样的
- 金骏眉是什么茶,金骏眉茶叶冲泡的步骤是怎样的
- 宋朝赵构之后的皇帝是哪一位 北宋第三个第三位皇帝是谁
- 红茶泡茶步骤,红茶戚风蛋糕
- 花茶多少度水冲泡,花茶的冲泡步骤及方式
- 金骏眉是什么,金骏眉茶叶冲泡的步骤是怎样的
- HttpClient三个超时时间详解
- 简单网络的反向传播代码这么写就对了：分解步骤+完整实现