强连通分量与环的关系是什么?它的实际问题形式是什么?望高手解答!谢谢!
问题描述：
强连通分量与环的关系是什么?它的实际问题形式是什么?望高手解答!谢谢!
答
强连通分量是有向图中的部分点集及其边构成的子图,这个子图内任意点可互达,这个子图不一定是一个环结构,可能是网状的.实际常常用于拓扑排序之前,有强连通分量必定有环,无法拓扑排序,因此一般用Tarjan算法缩掉强连通分量,形成有向无环图